Fuzzy Turing machines revised

Abstract

Fuzzy Turing machines and fuzzy languages were introduced by Zadeh, Lee and Santos in nineteen seventies. Unfortunately, it appears that from computability point of view their model is too powerful --- its nondeterministic version accepts non--recursively enumerable fuzzy languages. Moreover, from the viewpoint of the modern fuzzy logic theory the model is too restrictive since it is defined only for a specific $t$-norm (G\"odel norm). Therefore we propose a generalization of the original model that is based on rigorous mathematical fundamentals of fuzzy logic. Its acceptance criterion is modified so that the resulting model obeys the Church--Turing Thesis.