پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 31 |
| تعداد شمارهها | 834 |
| تعداد مقالات | 8,015 |
| تعداد مشاهده مقاله | 14,853,734 |
| تعداد دریافت فایل اصل مقاله | 9,587,187 |
Some improvements in fuzzy turing machines | ||
| Iranian Journal of Fuzzy Systems | ||
| مقاله 5، دوره 16، شماره 1، فروردین و اردیبهشت 2019، صفحه 49-60 اصل مقاله (339.21 K) | ||
| نوع مقاله: Original Manuscript | ||
| شناسه دیجیتال (DOI): 10.22111/ijfs.2019.4483 | ||
| نویسنده | ||
| Hadi Farahani* | ||
| Shahid Beheshti University | ||
| چکیده | ||
| 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 | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 1,189 تعداد دریافت فایل اصل مقاله: 477 |
||