Fuzzy and Intuitionistic Fuzzy Turing Machines

Article type: Research Article

Authors: Moniri, Morteza

Affiliations: Department of Mathematics, Shahid Beheshti University, G. C., Evin, Tehran, Iran. [email protected]

Note: [] Address for correspondence: School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O.Box 19395-5746, Tehran, Iran This research was in part supported by a grant from IPM (No. 90030119)

Abstract: First we define a new class of fuzzy Turing machines that we call Generalized Fuzzy Turing Machines. Our machines are equipped with rejecting states as well as accepting states. While we use a t-norm for computing degrees of accepting or rejecting paths, we use its dual t-conorm for computing the accepting or rejecting degrees of inputs. We naturally define when a generalized fuzzy Turing machine accepts or decides a fuzzy language. We prove that a fuzzy language L is decidable if and only if L and its complement are acceptable. Moreover, to each r.e. or co-r.e language L, we naturally correspond a fuzzy language which is acceptable by a generalized fuzzy Turing machine. A converse to this result is also proved. We also consider Atanasov's intuitionistic fuzzy languages and introduce a version of fuzzy Turing machine for studying their computability theoretic properties.

Keywords: Theory of Computing, Fuzzy Language, Fuzzy Turing Machine, Generalized Fuzzy Turing Machine, Intuitionistic Fuzzy Turing Machine

DOI: 10.3233/FI-2013-812

Journal: Fundamenta Informaticae, vol. 123, no. 3, pp. 305-315, 2013