Approximation and universality of fuzzy Turing machines

作者：Li YongMing^*

来源：Science in China - Series F: Information Sciences , 2008, 51(10): 1445-1465.

DOI：10.1007/s11432-008-0089-y

• fuzzy Turing machine
• fuzzy recursively enumerable language
• fuzzy recursive language
• universal fuzzy Turing machine
• fuzzy algorithm

Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-* composition 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 Turing 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.

• 出版日期2008-10
• 单位陕西师范大学