Several equivalent formulations of fuzzy Turing machines, including fuzzy nondeterministic Turing machines(FNTM), fuzzy nondeterministic Turing machines with crisp transition function (FNTMc) and multi-tape fuzzy Turing machines, are given. Then the notions of fuzzy recursively enumerable languages and fuzzy recursive languages are defined in terms of FNTMs. The level characterizations of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited. It is shown that there is no universal fuzzy Turing machine that can simulate any fuzzy Turing machine on it. But if the membership degree of fuzzy sets is restricted to a fixed finite subset D of ［0,1］, there is a (restricted) universal fuzzy Turing machine which can simulate any restricted fuzzy Turing machine (with membership degrees in D) on it. Furthermore, the restricted universal fuzzy Turing machine can approximate any fuzzy Turing machine with a given accuracy, that is to say, a universal fuzzy Turing machine exists in the approximate sense.

fuzzy algorithm; fuzzy computation; fuzzy Turing machine; universal fuzzy Turing machine