«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina.»

Minsky, Melzak-Lambek va Shepherdson-Sturgis modellari ko'pchilikka "lentani kesib tashladilar"

Xo'sh, nima uchun "tasmani kesmaysizlar", shunda ularning har biri cheksiz uzun (har qanday o'lchamdagi butun sonni sig'dirish uchun), lekin chap tomonda va shu uchta lentani "Post-Turing (ya'ni Vangga o'xshash) lentalar" deb nomlang? Alohida boshlar chapga (pasayish uchun) va o'ngga (o'sish uchun) siljiydi. Bir ma'noda boshlar birlashtirilgan belgilarning "ustunlar tepasini" bildiradi. Yoki Minsky (1961) va Hopkroft va Ullman (1979, p. 171ff) da lenta har doim bo'sh bo'ladi, faqat chap tomonidagi belgi bundan mustasno - hech qachon bosh hech qachon bosilmaydi yoki o'chirilmaydi.
Biz ko'rsatmalarimizni yozishda ehtiyot bo'lishimiz kerak, shunda nolga o'tish va sakrash sinab ko'rishi mumkin oldin biz kamaytiramiz, aks holda bizning mashinamiz "oxiridan yiqilib" yoki "oxirigacha to'qnashadi" - bizda qisman funktsiya. Kamayishdan oldin bizning mashinamiz har doim shunday savol berishi kerak: "Tasma / taymer bo'shmi? Agar shunday bo'lsa, men kamaytirolmayman, aks holda men qila olaman."
(Im-) to'g'ri ayirboshlashga misol uchun qarang Qisman funktsiya.
Minskiy (1961) va Shepherdson-Sturgis (1963) shuni isbotlaydiki, faqat bir nechta lenta, hattoki bittasi ham baribir mashinaning Turing ekvivalenti bo'lishiga imkon beradi IF lentadagi ma'lumotlar a sifatida ifodalanadi Gödel raqami (yoki boshqa noyob kodlanadigan-dekodlanadigan raqam); bu raqam hisoblash davom etishi bilan rivojlanib boradi. Hisoblagichni kodlaydigan Gödel raqami bo'lgan bitta lenta versiyasida (i) Gödel raqamini doimiyga ("2" yoki "3") ko'paytirishi va (ii) doimiyga ("2" raqamlariga) bo'linishi kerak. yoki "3") va agar qoldiq nol bo'lsa, sakrab chiqing. Minsky (1967) ushbu g'alati ko'rsatmalar to'plamiga bo'lgan ehtiyojni {INC (r), JZDEC (r, z)} ga va agar ikkita lenta mavjud bo'lsa, {CLR (r), J (r)} ga bo'lgan ehtiyojni yumshatish mumkinligini ko'rsatmoqda. . Biroq, sodda Gödelizatsiya talab qilinadi. Shunga o'xshash natija ularning RASP modeliga nisbatan Elgot-Robinson (1964) da paydo bo'ladi.