کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
390968 | 661324 | 2009 | 22 صفحه PDF | دانلود رایگان |

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-r.e. 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 distributive lattice with a compact metric, we also show that a 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 (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.
Journal: Fuzzy Sets and Systems - Volume 160, Issue 23, 1 December 2009, Pages 3453-3474