On the computing power of 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, recursively enumerable (r.e.) sets and universality. FTMs are first regarded as acceptors. It has recently been shown by J. Wiederma...

Descripción completa

Detalles Bibliográficos
Autor principal:	Figueira, Santiago Daniel
Publicado:	2008
Materias:	Fuzzy function Fuzzy set Fuzzy Turing machine Recursively enumerable set Universal machine Computational efficiency Computer programming languages Recursive functions Transducers Turing machines Fuzzy functions Recursively enumerable sets Universal machines Fuzzy sets
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01650114_v159_n9_p1072_Bedregal http://hdl.handle.net/20.500.12110/paper_01650114_v159_n9_p1072_Bedregal
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_01650114_v159_n9_p1072_Bedregal
record_format	dspace
spelling	paper:paper_01650114_v159_n9_p1072_Bedregal2023-06-08T15:14:33Z On the computing power of fuzzy Turing machines Figueira, Santiago Daniel Fuzzy function Fuzzy set Fuzzy Turing machine Recursively enumerable set Universal machine Computational efficiency Computer programming languages Recursive functions Transducers Turing machines Fuzzy functions Fuzzy Turing machine Recursively enumerable sets Universal 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, recursively enumerable (r.e.) sets and universality. FTMs are first regarded as acceptors. It has recently been shown by J. Wiedermann 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. We do the same thing for n-r.e. set. It is shown that there is no universal fuzzy machine, and "universality" is analyzed for smaller classes of FTMs. We 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. © 2007 Elsevier B.V. All rights reserved. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2008 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01650114_v159_n9_p1072_Bedregal http://hdl.handle.net/20.500.12110/paper_01650114_v159_n9_p1072_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	Fuzzy function Fuzzy set Fuzzy Turing machine Recursively enumerable set Universal machine Computational efficiency Computer programming languages Recursive functions Transducers Turing machines Fuzzy functions Fuzzy Turing machine Recursively enumerable sets Universal machines Fuzzy sets
spellingShingle	Fuzzy function Fuzzy set Fuzzy Turing machine Recursively enumerable set Universal machine Computational efficiency Computer programming languages Recursive functions Transducers Turing machines Fuzzy functions Fuzzy Turing machine Recursively enumerable sets Universal machines Fuzzy sets Figueira, Santiago Daniel On the computing power of fuzzy Turing machines
topic_facet	Fuzzy function Fuzzy set Fuzzy Turing machine Recursively enumerable set Universal machine Computational efficiency Computer programming languages Recursive functions Transducers Turing machines Fuzzy functions Fuzzy Turing machine Recursively enumerable sets Universal 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, recursively enumerable (r.e.) sets and universality. FTMs are first regarded as acceptors. It has recently been shown by J. Wiedermann 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. We do the same thing for n-r.e. set. It is shown that there is no universal fuzzy machine, and "universality" is analyzed for smaller classes of FTMs. We 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. © 2007 Elsevier B.V. All rights reserved.
author	Figueira, Santiago Daniel
author_facet	Figueira, Santiago Daniel
author_sort	Figueira, Santiago Daniel
title	On the computing power of fuzzy Turing machines
title_short	On the computing power of fuzzy Turing machines
title_full	On the computing power of fuzzy Turing machines
title_fullStr	On the computing power of fuzzy Turing machines
title_full_unstemmed	On the computing power of fuzzy Turing machines
title_sort	on the computing power of fuzzy turing machines
publishDate	2008
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01650114_v159_n9_p1072_Bedregal http://hdl.handle.net/20.500.12110/paper_01650114_v159_n9_p1072_Bedregal
work_keys_str_mv	AT figueirasantiagodaniel onthecomputingpoweroffuzzyturingmachines
_version_	1768546343208353792

On the computing power of fuzzy Turing machines

Ejemplares similares