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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2006
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 07090caa a22007457a 4500 | ||
|---|---|---|---|
| 001 | PAPER-7090 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203649.0 | ||
| 008 | 190411s2006 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-33745624272 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Bedregal, B.R.C. | |
| 245 | 1 | 0 | |a Classical computability and fuzzy Turing machines |
| 260 | |c 2006 | ||
| 270 | 1 | 0 | |m Bedregal, B.R.C.; Federal University of Rio Grande do Norte, Department of Informatics and Applied Mathematics, Laboratory of Logic and Computational Intelligence, Natal-RN, 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 Biacino, L., Gerla, G., Fuzzy subsets: A constructive approach (1992) Fuzzy Sets and Systems, 45, pp. 161-168 | ||
| 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 Demirci, M., Fuzzy functions and their applications (2000) Journal of Mathematical Analysis and Appliactions, 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 Fenner, S.A., Fortnow, L., Naik, A.V., Rogers, J.D., Inverting onto functions (2003) Information and Computation, 186 (1), pp. 90-103 | ||
| 504 | |a Gerla, G., (2001) Fusszy Logic: Mathematical Tools for Approximate Reasoning, , Springer-Verlag, Berlin Heidelberg New York | ||
| 504 | |a Goldin, D.Q., Smolka, S.A., Attie, P.C., Sonderegger, E.L., Turing machines, transition systems and interaction (2004) Information and Computation, 194, pp. 101-128 | ||
| 504 | |a Harkleroad, L., Fuzzy recursion, ret's and isols (1984) Zeitschrift fur Math. Logik und Grundlagen der Mathematik, 30, pp. 425-436 | ||
| 504 | |a Harrison, M.A., (1978) Introduction to Formal Language Theory, , Addison-Wesley publishing, Reading, Massachusetts | ||
| 504 | |a Hopcroft, J.E., Ullman, J.D., (1979) Introduction to Automata Theory, Languages and Computation, , Addison-Wesley publishing, Reading, Massachusetts | ||
| 504 | |a Lee, E.T., Zadeh, L.A., Note on fuzzy languages (1969) Information Sciences, 1 (4), pp. 421-434 | ||
| 504 | |a Linz, P., (2001) An Introduction to Formal Language and Automata, , Jones and Bartlett Publisher | ||
| 504 | |a Moraga, C., Towards a fuzzy computability? (1999) Mathware & Soft Computing, 6, pp. 163-172 | ||
| 504 | |a Morales-Bueno, R., Conejo, R., Prez-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 Porfilieva, 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., Fuzzy algorithms (1970) Information and Control, 17, pp. 326-339 | ||
| 504 | |a Santos, E., Fuzzy and probabilistic programs (1976) Information Sciences, 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., (1987) Recursively Enumerable Sets and Degrees, , Springer-Verlag, Berlin Heidelberg New York | ||
| 504 | |a Weihrauch, K., (2000) Computable Analysis - An Introduction, , Springer Verlag, Berlin Heildelberg New York | ||
| 504 | |a Wiedermann, J., Fuzzy Turing machines revised (2002) Computating and Informatics, 21 (3), pp. 1-13 | ||
| 504 | |a Wiedermann, J., Characterizing the super-Turing computing power and efficiency of classical fuzzey Turing machines (2004) Theoretical Computer Science, 317, pp. 61-69 | ||
| 504 | |a Zadeh, L.A., Fuzzy algorithms (1968) Information and Control, 2, pp. 94-102 | ||
| 504 | |a Zimmermann, H.J., (2001) Fuzzy Set Theory and Its Applications. 4th Edition, , Kluwer Academic Publishers, Dorbrecht Boston LondonA4 - Centro Latinoamericano de Estudios en Informatica, CLEI; U. Chile, Centro de Modelamiento Matematico; CONICYT via grant Anillo en Redes; International Federation for Information Processing, IFIP | ||
| 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, 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. |l eng | |
| 593 | |a Federal University of Rio Grande do Norte, Department of Informatics and Applied Mathematics, Laboratory of Logic and Computational Intelligence, Natal-RN, Brazil | ||
| 593 | |a University of Buenos Aires, Department of Computer Science, FCEyN, Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a MATHEMATICAL MODELS |
| 690 | 1 | 0 | |a RECURSIVE FUNCTIONS |
| 690 | 1 | 0 | |a SET THEORY |
| 690 | 1 | 0 | |a TRANSDUCERS |
| 690 | 1 | 0 | |a CLASSICAL RECURSION CONCEPTS |
| 690 | 1 | 0 | |a COMPUTABLE FUZZY FUNCTION |
| 690 | 1 | 0 | |a COMPUTATIONAL POWER |
| 690 | 1 | 0 | |a FUZZY TURING MACHINES |
| 690 | 1 | 0 | |a FUZZY SETS |
| 700 | 1 | |a Figueira, S. | |
| 711 | 2 | |c Valdivia |d 20 March 2006 through 24 March 2006 |g Código de la conferencia: 67649 | |
| 773 | 0 | |d 2006 |g v. 3887 LNCS |h pp. 154-165 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 354032755X |z 9783540327554 |t LATIN 2006: Theoretical Informatics - 7th Latin American Symposium | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-33745624272&doi=10.1007%2f11682462_18&partnerID=40&md5=02dc8bd8b00f05b92a665f63e28fa52c |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/11682462_18 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v3887LNCS_n_p154_Bedregal |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3887LNCS_n_p154_Bedregal |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v3887LNCS_n_p154_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 | ||
| 963 | |a VARI | ||
| 999 | |c 68043 | ||