TY - JOUR
ID - 4483
TI - Some improvements in fuzzy turing machines
JO - Iranian Journal of Fuzzy Systems
JA - IJFS
LA - en
SN - 1735-0654
AU - Farahani, Hadi
AD - Shahid Beheshti University
Y1 - 2019
PY - 2019
VL - 16
IS - 1
SP - 49
EP - 60
KW - Theory of computation
KW - Extended fuzzy Turing machine
KW - Indeterminacy state
KW - Halting Problem
DO - 10.22111/ijfs.2019.4483
N2 - 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.
UR - https://ijfs.usb.ac.ir/article_4483.html
L1 - https://ijfs.usb.ac.ir/article_4483_fc68ff7f9208bc5cda04710e7bf9644d.pdf
ER -