论文部分内容阅读
Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computa-tions. In this paper we give several different formulations of fuzzy Turing machine,which correspond to nondeterministic fuzzy Turing machine using max-composi-tion for some t-norm (or NFTM ,for short),nondeterministic fuzzy Turing machine (or NFTM),deterministic fuzzy Turing machine (or DFTM),and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Tur-ing machines are obtained. First,it is shown that NFTM ,NFTM,and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm does not satisfy finite generated condition,but are equivalent in the approximation sense. That is to say,we can approximate an NFTM by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second,we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM on it with a given accuracy.
Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computa-tions. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-composi-tion for some t-norm (or NFTM , for short), nondeterministic fuzzy Turing machine (or NFTM), deterministic fuzzy Turing machine (or DFTM), and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Tur-ing machines are obtained. First, it is shown that NFTM, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary re languages an d recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM on it with a given accuracy.