«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina.»

II BOB Turing mashinasi

2.1 Hisoblashning matematik modeli
Turing mashinasi a hisoblashning matematik modeli bu belgilaydi mavhum mashina,^[1] lenta tasmasidagi belgilarni qoidalar jadvaliga muvofiq boshqaradi.^[2] Modelning soddaligiga qaramay, har qanday berilgan kompyuter algoritmi, algoritm mantig'ini simulyatsiya qilishga qodir Turing mashinasi.^[3]
Mashina cheksiz ishlaydi^[4] bo'lingan xotira lentasi diskret "hujayralar".^[5] Mashina "boshini" hujayra ustiga qo'yadi va "o'qiydi" yoki "skanerlaydi"^[6] belgi bor. Keyin, belgi va mashinaning o'z holatiga ko'ra "cheklangan jadval"^[7] foydalanuvchi tomonidan ko'rsatilgan ko'rsatmalar, (i) mashina katakchada belgini (masalan, sonli alfavitdagi raqam yoki harfni) yozadi (ba'zi modellar belgini o'chirishga imkon beradi yoki yozilmaydi),^[8] keyin (ii) yoki lentani bitta katakchani chapga yoki o'ngga siljitadi (ba'zi modellar harakatga yo'l qo'ymaydi, ba'zi modellar boshni siljitadi),^[9] u holda (iii) (kuzatilgan belgi va jadvaldagi mashinaning o'z holati bilan belgilanadi) yoki keyingi ko'rsatmaga o'tadi yoki hisoblashni to'xtatadi.^[10]
Turing mashinasi 1936 yilda ixtiro qilingan Alan Turing,^[11][12] kim uni "a-mashina" (avtomatik mashina) deb atagan.^[13] Ushbu model yordamida Turing ikkita savolga salbiy javob bera oldi: (1) tasmasidagi har qanday o'zboshimchalikli mashinaning "aylana" ekanligini (masalan, qotib qolishi yoki hisoblash vazifasini davom ettira olmasligini) aniqlaydigan mashina mavjudmi? Xuddi shunday, (2) tasmada har qanday ixtiyoriy mashina berilgan belgini bosib chiqaradimi yoki yo'qligini aniqlaydigan mashina mavjudmi?^[14][15] Shunday qilib, o'zboshimchalik bilan hisoblashga qodir bo'lgan juda sodda qurilmaning matematik tavsifini berish orqali u umuman hisoblash xususiyatlarini - va xususan, hisoblanmaslik ning Entscheidungsproblem ("qaror bilan bog'liq muammo").^[16]
Turing mashinalari mexanik hisoblash kuchi bo'yicha asosiy cheklovlar mavjudligini isbotladi.^[17] Ular o'zboshimchalik bilan hisob-kitoblarni ifoda eta olsalar-da, ularning minimalist dizayni ularni amalda hisoblash uchun yaroqsiz qiladi: haqiqiy dunyo kompyuterlar Turing mashinalaridan farqli o'laroq foydalanadigan turli xil dizaynlarga asoslangan tezkor kirish xotirasi.