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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2008
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 09356caa a22009977a 4500 | ||
|---|---|---|---|
| 001 | PAPER-5957 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203538.0 | ||
| 008 | 190411s2008 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-39949083043 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a FSSYD | ||
| 100 | 1 | |a Bedregal, B.C. | |
| 245 | 1 | 3 | |a On the computing power of fuzzy Turing machines |
| 260 | |c 2008 | ||
| 270 | 1 | 0 | |m Bedregal, B.C.; Departamento de Informática e Matemática Aplicada, Laboratório de Lógica e Inteligência Computacional, Universidade Federal do Rio Grande do Norte, Campus Universitário s/n, Lagoa Nova, Natal-RN, CEP 59.072-970, Brazil; email: bedregal@dimap.ufrn.br |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Alsina, C., Trillas, E., Valverde, L., On non-distributive logical connectives for fuzzy set theory (1980) Busefal, 3, pp. 18-29 | ||
| 504 | |a B.C. Bedregal, B.M. Acióly, A computability on the interval space: a domain approach, in: Proc. XXIII Conf. Latinoamericana de Informática, Vol. I, Valparaíso-Chile, 1997, pp. 107-116; Biacino, L., Gerla, G., Fuzzy subsets: a constructive approach (1992) Fuzzy Sets and Systems, 45, pp. 161-168 | ||
| 504 | |a Biacino, L., Gerla, G., Fuzzy logic, continuity and effectiveness (2002) Arch. Math. Logic, 41, pp. 643-667 | ||
| 504 | |a Blum, L., Shub, M., Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines (1989) Bull. Amer. Math. Soc., 21 (1), pp. 1-46 | ||
| 504 | |a Clares, B., Delgado, M., Introduction of the concept of recursiveness of fuzzy functions (1987) Fuzzy Sets and Systems, 21, pp. 301-310 | ||
| 504 | |a A.C.R. Costa, G.P. Dimuro, Interactive computation: stepping stone in the pathway from classical to developmental computation, Electronic Notes in Theoretical Computer Science, Vol. 141(5), 2005, pp. 5-31; Demirci, M., Fuzzy functions and their applications (2000) J. Math. Anal. Appl., 252 (1), pp. 495-517 | ||
| 504 | |a Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer (1985) Proc. Roy. Soc. London Ser. A, 400, pp. 97-117 | ||
| 504 | |a Dubois, D.J., Prade, H., (1980) Fuzzy Sets and Systems: Theory and Applications, , Academic Press, Inc., New York | ||
| 504 | |a Gerla, G., (2001) Fuzzy Logic: Mathematical Tools for Approximate Reasoning, , Kluwer Academic Publishers, Dordrecht | ||
| 504 | |a Gerla, G., Effectiveness and multivalued logics (2006) J. Symbolic Logic, 71, pp. 137-162 | ||
| 504 | |a Di Gianantonio, P., Real number computation and domain theory (1996) Inform. and Comput., 127, pp. 11-25 | ||
| 504 | |a Goldin, D.Q., Smolka, S.A., Attie, P.C., Sonderegger, E.L., Turing machines, transition systems and interaction (2004) Inform. and Comput., 194, pp. 101-128 | ||
| 504 | |a Grzegorczyk, A., On the definitions of computable real continuous functions (1957) Fund. Math., 44, pp. 61-71 | ||
| 504 | |a Harkleroad, L., Fuzzy recursion, ret's and isols (1984) Z. Math. Logik Grundlagen Math., 30, pp. 425-436 | ||
| 504 | |a Harrison, M.A., (1978) Introduction to Formal Language Theory, , Addison-Wesley, Reading, MA | ||
| 504 | |a Hájek, P., Fuzzy logic and arithmetical hierarchy (1995) Fuzzy Sets and Systems, 73, pp. 359-363 | ||
| 504 | |a Hopcroft, J.E., Ullman, J.D., (1979) Introduction to Automata Theory, Languages and Computation, , Addison-Wesley, Reading, MA | ||
| 504 | |a Klir, J., Yuan, B., (1995) Fuzzy Sets and Fuzzy Logics: Theory and Applications, , Prentice Hall PTR | ||
| 504 | |a Lee, E.T., Zadeh, L.A., Note on fuzzy languages (1969) Inform. Sci., 4 (1), pp. 421-434 | ||
| 504 | |a Lee, K.H., (2005) First Course on Fuzzy Theory and Applications, , Springer, Berlin | ||
| 504 | |a Linz, P., (2001) An Introduction to Formal Language and Automata, , Jones and Bartlett Publisher | ||
| 504 | |a Menger, K., Statistical metrics (1942) Proc. Nat. Acad. Sci., 37, pp. 535-537 | ||
| 504 | |a Moraga, C., Towards a fuzzy computability? (1999) Mathware & Soft Comput., 6, pp. 163-172 | ||
| 504 | |a Morales-Bueno, R., Conejo, R., Pérez de-la Cruz, J.L., Triguero-Ruiz, F., On a class of fuzzy computable functions (2001) Fuzzy Sets and Systems, 121, pp. 505-522 | ||
| 504 | |a Morderson, J.N., Malik, D.S., (2002) Fuzzy Automata and Languages: Theory and Applications, , Chapman & Hall, CRC, London, Boca Raton, FL | ||
| 504 | |a Negoita, C.V., Ralescu, D.A., (1975) Applications of Fuzzy Sets to Systems Analysis, , Birkhaeuser, Basel | ||
| 504 | |a Novak, E., The real number model in numerical analysis (1995) J. Complexity, 11 (1), pp. 57-73 | ||
| 504 | |a Perfilieva, I., Fuzzy function as an approximate solution to a system of fuzzy relation equations (2004) Fuzzy Sets and Systems, 147, pp. 363-383 | ||
| 504 | |a Santos, E.S., Fuzzy algorithms (1970) Inform. and Control, 17, pp. 326-339 | ||
| 504 | |a Santos, E.S., Fuzzy and probabilistic programs (1976) Inform. Sci., 10, pp. 331-335 | ||
| 504 | |a Schweizer, B., Sklar, A., Associative functions and abstract semigroups (1963) Publ. Math. Debrecen, 10, pp. 69-81 | ||
| 504 | |a Soare, R.I., (1987) Recursively Enumerable Sets and Degrees, , Springer, Berlin | ||
| 504 | |a Weihrauch, K., (2000) Computable Analysis-An Introduction, , Springer, Berlin | ||
| 504 | |a Wiedermann, J., Fuzzy Turing machines revised (2002) Comput. Artificial Intelligence, 21 (3), pp. 1-13 | ||
| 504 | |a Wiedermann, J., Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines (2004) Theoret. Comput. Sci., 317, pp. 61-69 | ||
| 504 | |a Zadeh, L.A., Fuzzy algorithms (1968) Inform. and Control, 2, pp. 94-102 | ||
| 504 | |a Zimmermann, H.J., (2001) Fuzzy Set Theory and its Applications. fourth ed., , Kluwer Academic Publishers, Dordrecht | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq | ||
| 536 | |a Detalles de la financiación: 307879/2006-2, 470871/2004-0 | ||
| 536 | |a Detalles de la financiación: Fundación YPF | ||
| 536 | |a Detalles de la financiación: Alzheimer Society of B.C. | ||
| 536 | |a Detalles de la financiación: We thank the anonymous referees for their comments and suggestions which helped to improve the paper. B.C. Bedregal acknowledges CNPq (Brazilian Research Council) under process numbers 470871/2004-0 and 307879/2006-2. S. Figueira is partially supported by a grant of Fundación YPF, Argentina. He also acknowledges CONICET. | ||
| 593 | |a Departamento de Informática e Matemática Aplicada, Laboratório de Lógica e Inteligência Computacional, Universidade Federal do Rio Grande do Norte, Campus Universitário s/n, Lagoa Nova, Natal-RN, CEP 59.072-970, Brazil | ||
| 593 | |a Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellon I, Ciudad Universitaria, C1428EGA Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a FUZZY FUNCTION |
| 690 | 1 | 0 | |a FUZZY SET |
| 690 | 1 | 0 | |a FUZZY TURING MACHINE |
| 690 | 1 | 0 | |a RECURSIVELY ENUMERABLE SET |
| 690 | 1 | 0 | |a UNIVERSAL MACHINE |
| 690 | 1 | 0 | |a COMPUTATIONAL EFFICIENCY |
| 690 | 1 | 0 | |a COMPUTER PROGRAMMING LANGUAGES |
| 690 | 1 | 0 | |a RECURSIVE FUNCTIONS |
| 690 | 1 | 0 | |a TRANSDUCERS |
| 690 | 1 | 0 | |a TURING MACHINES |
| 690 | 1 | 0 | |a FUZZY FUNCTIONS |
| 690 | 1 | 0 | |a FUZZY TURING MACHINE |
| 690 | 1 | 0 | |a RECURSIVELY ENUMERABLE SETS |
| 690 | 1 | 0 | |a UNIVERSAL MACHINES |
| 690 | 1 | 0 | |a FUZZY SETS |
| 700 | 1 | |a Figueira, S. | |
| 773 | 0 | |d 2008 |g v. 159 |h pp. 1072-1083 |k n. 9 |p Fuzzy Sets Syst |x 01650114 |w (AR-BaUEN)CENRE-313 |t Fuzzy Sets and Systems | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-39949083043&doi=10.1016%2fj.fss.2007.10.013&partnerID=40&md5=5d78b64e31ebbaa1be1bae6c54d69bcb |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.fss.2007.10.013 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_01650114_v159_n9_p1072_Bedregal |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01650114_v159_n9_p1072_Bedregal |y Registro en la Biblioteca Digital |
| 961 | |a paper_01650114_v159_n9_p1072_Bedregal |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 66910 | ||