2017/07/16 by Hadi Farahani, Farahani, Hadi
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1707.05311
openalex publication_date 2017/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we modify some previous definitions of fuzzy Turing machines to define the notions of accepting and rejecting degrees of inputs, computationally. We use a BFS-based search method and obtain an upper level bound to guarantee the existence of accepting and rejecting degrees. We show that fuzzy, generalized fuzzy and classical Turing machines have the same computational power. Next, we introduce the class of Extended Fuzzy Turing Machines equipped with indeterminacy states. These machines are used to catch some types of loops of the classical Turing machines. Moreover, to each r.e. or co-r.e language, we correspond a fuzzy language which is indeterminable by an extended fuzzy Turing machine.