Automata theory based on complete residuated lattice-valued logic: Turing machines

Automata theory based on complete residuated lattice-valued logic, called L -valued finite automata ( L -VFAs), has been established by the second author in 2001. In view of the importance of Turing machines, in this paper, we establish a theory of Turing machines based on complete residuated lattice-valued logic, which is a continuation of L -VFAs. First, we give the definition of L -valued nondeterministic Turing machines ( L -NTMs), and observe that the multitape L -NTMs have the same language-recognizing power as the single-tape L -NTMs. We give some related properties of L -valued Turing machines, and discuss computing with fuzzy letters via L -valued Turing machines. Second, we introduce the concepts of L -valued recursively enumerable languages and L -valued recursive languages, and obtain some equivalent relations. Some results concerning the characterization of n-recursively enumerable sets are given, and the super-computing power of L -valued Turing machines is investigated. We also prove that L -valued deterministic Turing machines and L -NTMs are not equivalent in the sense of recognizing or deciding languages. Finally, we show that there is no universal L -valued Turing machine. However, a universal L -valued Turing machine exists if the membership degrees of L -valued sets are restricted to a finite complete residuated lattice with universal bounds 0 and 1.