Classical computability and fuzzy Turing machines

We work with fuzzy Turing machines (FTMS) and we study the relationship between this computational model and classical recursion concepts such as computable functions, r.e. sets and universality. FTMS are first regarded as acceptors. It has recently been shown in [23] that these machines have more c...

Descripción completa

Detalles Bibliográficos
Autor principal:	Figueira, Santiago Daniel
Publicado:	2006
Materias:	Computational complexity Mathematical models Recursive functions Set theory Transducers Classical recursion concepts Computable fuzzy function Computational power Fuzzy Turing machines Fuzzy sets
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3887LNCS_n_p154_Bedregal http://hdl.handle.net/20.500.12110/paper_03029743_v3887LNCS_n_p154_Bedregal
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03029743_v3887LNCS_n_p154_Bedregal
record_format	dspace
spelling	paper:paper_03029743_v3887LNCS_n_p154_Bedregal2023-06-08T15:28:23Z Classical computability and fuzzy Turing machines Figueira, Santiago Daniel Computational complexity Mathematical models Recursive functions Set theory Transducers Classical recursion concepts Computable fuzzy function Computational power Fuzzy Turing machines Fuzzy sets We work with fuzzy Turing machines (FTMS) and we study the relationship between this computational model and classical recursion concepts such as computable functions, r.e. sets and universality. FTMS are first regarded as acceptors. It has recently been shown in [23] that these machines have more computational power than classical Turing machines. Still, the context in which this formulation is valid has an unnatural implicit assumption, We settle necessary and sufficient conditions for a language to be r.e., by embedding it in a fuzzy language recognized by a FTM and we do the same thing for difference r.e. sets, a class of "harder" sets in terms of computability. It is also shown that there is no universal FTM. We also argue for a definition of computable fuzzy function, when FTMS are understood as transducers. It is shown that, in this case, our notion of computable fuzzy function coincides with the classical one. © Springer-Verlag Berlin Heidelberg 2006. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3887LNCS_n_p154_Bedregal http://hdl.handle.net/20.500.12110/paper_03029743_v3887LNCS_n_p154_Bedregal
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Computational complexity Mathematical models Recursive functions Set theory Transducers Classical recursion concepts Computable fuzzy function Computational power Fuzzy Turing machines Fuzzy sets
spellingShingle	Computational complexity Mathematical models Recursive functions Set theory Transducers Classical recursion concepts Computable fuzzy function Computational power Fuzzy Turing machines Fuzzy sets Figueira, Santiago Daniel Classical computability and fuzzy Turing machines
topic_facet	Computational complexity Mathematical models Recursive functions Set theory Transducers Classical recursion concepts Computable fuzzy function Computational power Fuzzy Turing machines Fuzzy sets
description	We work with fuzzy Turing machines (FTMS) and we study the relationship between this computational model and classical recursion concepts such as computable functions, r.e. sets and universality. FTMS are first regarded as acceptors. It has recently been shown in [23] that these machines have more computational power than classical Turing machines. Still, the context in which this formulation is valid has an unnatural implicit assumption, We settle necessary and sufficient conditions for a language to be r.e., by embedding it in a fuzzy language recognized by a FTM and we do the same thing for difference r.e. sets, a class of "harder" sets in terms of computability. It is also shown that there is no universal FTM. We also argue for a definition of computable fuzzy function, when FTMS are understood as transducers. It is shown that, in this case, our notion of computable fuzzy function coincides with the classical one. © Springer-Verlag Berlin Heidelberg 2006.
author	Figueira, Santiago Daniel
author_facet	Figueira, Santiago Daniel
author_sort	Figueira, Santiago Daniel
title	Classical computability and fuzzy Turing machines
title_short	Classical computability and fuzzy Turing machines
title_full	Classical computability and fuzzy Turing machines
title_fullStr	Classical computability and fuzzy Turing machines
title_full_unstemmed	Classical computability and fuzzy Turing machines
title_sort	classical computability and fuzzy turing machines
publishDate	2006
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3887LNCS_n_p154_Bedregal http://hdl.handle.net/20.500.12110/paper_03029743_v3887LNCS_n_p154_Bedregal
work_keys_str_mv	AT figueirasantiagodaniel classicalcomputabilityandfuzzyturingmachines
_version_	1768545832213151744

Classical computability and fuzzy Turing machines

Ejemplares similares