کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
390808 661304 2008 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the computing power of fuzzy Turing machines
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
On the computing power of fuzzy Turing machines
چکیده انگلیسی

We work with fuzzy Turing machines (FTMs) and we study the relationship between this computational model and classical recursion concepts such as computable functions, recursively enumerable (r.e.) sets and universality. FTMs are first regarded as acceptors. It has recently been shown by J. Wiedermann that these machines have more computational power than classical Turing machines. Still, the context in which this formulation is valid has an unnatural implicit assumption. We settle necessary and sufficient conditions for a language to be r.e., by embedding it in a fuzzy language recognized by a FTM. We do the same thing for n-r.e. set. It is shown that there is no universal fuzzy machine, and “universality” is analyzed for smaller classes of FTMs. We argue for a definition of computable fuzzy function, when FTMs are understood as transducers. It is shown that, in this case, our notion of computable fuzzy function coincides with the classical one.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Fuzzy Sets and Systems - Volume 159, Issue 9, 1 May 2008, Pages 1072-1083