Some improvements in fuzzy turing machines

In this paper, we improve some previous definitions of fuzzy-type Turing machines to obtain degrees of accepting and rejecting in a computational manner. We apply a BFS-based search method and some level’s upper bounds to propose a computational process in calculating degrees of accepting and rejecting. Next, we introduce the class of Extended Fuzzy Turing Machines equipped with indeterminacy states. These states are used to characterize the loops of classical Turing machines in a mathematical sense. In the sequel, as well as the notions of acceptable and decidable languages, we define the new notion of indeterminable language. An indeterminable language corresponds to non-halting runs of a machine. Afterwards, we show that there is not any universal extended machine; which concludes that these machines cannot solve the halting problem. Also, we show that our extended machines and classical Turing machines have the same computational power. Then, we define the new notion of semi-universality and prove that there exists a semi-universal extended machine. This machine can indeterminate the complement of classical halting problem. Moreover, to each r.e or co-r.e language, we correspond a language that is related to some extended fuzzy Turing machines.

کلیدواژه ها:

Theory of computation ، Extended fuzzy Turing machine ، Indeterminacy state ، Halting Problem