Abstract:
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.
Registro:
Documento: |
Artículo
|
Título: | Classical computability and fuzzy Turing machines |
Autor: | Bedregal, B.R.C.; Figueira, S. |
Ciudad: | Valdivia |
Filiación: | Federal University of Rio Grande do Norte, Department of Informatics and Applied Mathematics, Laboratory of Logic and Computational Intelligence, Natal-RN, Brazil University of Buenos Aires, Department of Computer Science, FCEyN, Buenos Aires, Argentina
|
Palabras clave: | Computational complexity; Mathematical models; Recursive functions; Set theory; Transducers; Classical recursion concepts; Computable fuzzy function; Computational power; Fuzzy Turing machines; Fuzzy sets |
Año: | 2006
|
Volumen: | 3887 LNCS
|
Página de inicio: | 154
|
Página de fin: | 165
|
DOI: |
http://dx.doi.org/10.1007/11682462_18 |
Título revista: | LATIN 2006: Theoretical Informatics - 7th Latin American Symposium
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3887LNCS_n_p154_Bedregal |
Referencias:
- Alsina, C., Trillas, E., Valverde, L., On non-distributive logical connectives for fuzzy set theory (1980) Busefal, 3, pp. 18-29
- Biacino, L., Gerla, G., Fuzzy subsets: A constructive approach (1992) Fuzzy Sets and Systems, 45, pp. 161-168
- Clares, B., Delgado, M., Introduction of the concept of recursiveness of fuzzy functions (1987) Fuzzy Sets and Systems, 21, pp. 301-310
- Demirci, M., Fuzzy functions and their applications (2000) Journal of Mathematical Analysis and Appliactions, 252 (1), pp. 495-517
- Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer (1985) Proc. Roy. Soc. London Ser. A, 400, pp. 97-117
- Fenner, S.A., Fortnow, L., Naik, A.V., Rogers, J.D., Inverting onto functions (2003) Information and Computation, 186 (1), pp. 90-103
- Gerla, G., (2001) Fusszy Logic: Mathematical Tools for Approximate Reasoning, , Springer-Verlag, Berlin Heidelberg New York
- 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
- Harkleroad, L., Fuzzy recursion, ret's and isols (1984) Zeitschrift fur Math. Logik und Grundlagen der Mathematik, 30, pp. 425-436
- Harrison, M.A., (1978) Introduction to Formal Language Theory, , Addison-Wesley publishing, Reading, Massachusetts
- Hopcroft, J.E., Ullman, J.D., (1979) Introduction to Automata Theory, Languages and Computation, , Addison-Wesley publishing, Reading, Massachusetts
- Lee, E.T., Zadeh, L.A., Note on fuzzy languages (1969) Information Sciences, 1 (4), pp. 421-434
- Linz, P., (2001) An Introduction to Formal Language and Automata, , Jones and Bartlett Publisher
- Moraga, C., Towards a fuzzy computability? (1999) Mathware & Soft Computing, 6, pp. 163-172
- 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
- Porfilieva, I., Fuzzy function as an approximate solution to a system of fuzzy relation equations (2004) Fuzzy Sets and Systems, 147, pp. 363-383
- Santos, E., Fuzzy algorithms (1970) Information and Control, 17, pp. 326-339
- Santos, E., Fuzzy and probabilistic programs (1976) Information Sciences, 10, pp. 331-335
- Schweizer, B., Sklar, A., Associative functions and abstract semigroups (1963) Publ. Math. Debrecen, 10, pp. 69-81
- Soare, R., (1987) Recursively Enumerable Sets and Degrees, , Springer-Verlag, Berlin Heidelberg New York
- Weihrauch, K., (2000) Computable Analysis - An Introduction, , Springer Verlag, Berlin Heildelberg New York
- Wiedermann, J., Fuzzy Turing machines revised (2002) Computating and Informatics, 21 (3), pp. 1-13
- Wiedermann, J., Characterizing the super-Turing computing power and efficiency of classical fuzzey Turing machines (2004) Theoretical Computer Science, 317, pp. 61-69
- Zadeh, L.A., Fuzzy algorithms (1968) Information and Control, 2, pp. 94-102
- 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
Citas:
---------- APA ----------
Bedregal, B.R.C. & Figueira, S.
(2006)
. Classical computability and fuzzy Turing machines. LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, 3887 LNCS, 154-165.
http://dx.doi.org/10.1007/11682462_18---------- CHICAGO ----------
Bedregal, B.R.C., Figueira, S.
"Classical computability and fuzzy Turing machines"
. LATIN 2006: Theoretical Informatics - 7th Latin American Symposium 3887 LNCS
(2006) : 154-165.
http://dx.doi.org/10.1007/11682462_18---------- MLA ----------
Bedregal, B.R.C., Figueira, S.
"Classical computability and fuzzy Turing machines"
. LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, vol. 3887 LNCS, 2006, pp. 154-165.
http://dx.doi.org/10.1007/11682462_18---------- VANCOUVER ----------
Bedregal, B.R.C., Figueira, S. Classical computability and fuzzy Turing machines. Lect. Notes Comput. Sci. 2006;3887 LNCS:154-165.
http://dx.doi.org/10.1007/11682462_18