Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines First we give several formulations of lattice-valued fuzzy Turing machines. including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines Second, we show that lattice-valued fuzzy Turing machines can recognize n-re sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributed lattice with a compact metric, we also show that it universal fuzzy Turing Machine exists in an approximate sense. This means. for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy Finally. we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (IP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (INP), and investigate their connections with P and NP We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines. (C) 2009 Elsevier B.V All rights reserved