Some improvements in fuzzy turing machines

Document Type : Original Manuscript

Author

Shahid Beheshti University

Abstract

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.

Keywords

References

[1] B. C. Bedregal, S. Figueira, On the computing power of fuzzy Turing machines, Fuzzy Sets and Systems, 159(2008), 1072–1083.
[2] L. Biacino, G. Gerla, Recursively enumerable L-sets, Mathematical Logic Quarterly, 33(2) (1987), 107–113.
[3] H. Farahani, Meta-type Fuzzy Computations and Fuzzy Complexity, Journal of Intelligent and Fuzzy Systems, 34 (2018), 81–92.
[4] G. Gerla, Sharpness relation and decidable fuzzy sets, IEEE Transactions on Automatic Control, 27(5) (1982), 1113–1113.
[5] P. Hájek, Metamathematics of Fuzzy Logic, Kluwer Academic Publishers, Dordrecht, 1998.
[6] L. Harkteroad, Fuzzy recursion. ret’s arid isols, Zeitschrift Math. Logik Grundlagen Math, 30 (1984), 425–430.
[7] E. T. Lee, L. A. Zadeh, Note on fuzzy languages, Information Sciences, 4(1) (1969), 421–434.
[8] M. Moniri, Fuzzy and Intuitionistic Fuzzy Turing Machines, Fundamenta Informaticae, 123 (2013), 305–315.
[9] E. S. Santos, Fuzzy algorithms, Information and Control, 17 (1970), 326–339.
[10] E. S. Santos, Fuzzy and probabilistic programs, Information Sciences, 10 (1976), 331–335.
[11] M. Sipser, Introduction to the Theory of Computation, 3rd Edition, Cengage Learning, Boston, MA, 2012.
[12] J. Wiedermann, Charactrizing the super-Turing power and efficiency of classical fuzzyTuringmachines,Theoretical Computer Science, 317 (2004), 61–69.
[13] J. Wiedermann, Fuzzy Turing machines revised, Computer Artificial Intelligence, 21(3) (2003), 1–13.
[14] L. A. Zadeh, Fuzzy algorithms, Information and Control, 2 (1968), 94–102.
[15] L. A. Zadeh, Fuzzy sets, Information and Control, 8 (1965), 338–353.
Iranian Journal of Fuzzy Systems
Volume 16, Issue 1
January and February 2019
Pages 49-60

Files

Share

How to cite

Statistics