«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina.»

(1954, 1957) Vang modeli: Post-Turing mashinasi

Vangning ishi davom etdi Emil Post(1936) qog'ozi va Vangni o'zining ta'rifiga olib bordi Wang B mashinasi- ikkita belgi Turingdan keyingi mashina faqat to'rtta atom ko'rsatmasiga ega hisoblash modeli:
{LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z}
Ushbu to'rtga ikkala Vang (1954, 1957) va keyin C.Y. Li (1961) Post to'plamidan yana bir ko'rsatmani ({ERASE}), so'ngra Postning shartsiz sakrashini (JUMP_to_ruction_z} (yoki ishlarni osonlashtirish uchun JUMP_IF_blank_to_instruction_z shartli sakrashni yoki ikkalasini) qo'shib qo'ydi. Li buni "W-machine" modeli deb nomladi. :
{LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [JUMP yoki JUMP_IF_blank]
Vang uning modeli Tyuring mashinalari nazariyasi va kompyuterning amaliy dunyosi o'rtasida "yaqinlashish" bo'lishiga umid bildirdi (63-bet).
Vangning ishi juda ta'sirli edi. Uni Minskiy (1961) va (1967), Melzak (1961), Shepherdson va Sturgis (1963) havolalarini topdik. Darhaqiqat, Shepherdson and Sturgis (1963) shunday deb ta'kidlaydilar:
"... biz Vang tomonidan tavsiya etilgan hisoblashning amaliy va nazariy jihatlari o'rtasidagi" yaqinlashuv "ni bir oz oldinga surishga harakat qildik" (218-bet).
Martin Devis pirovardida ushbu model Post-Turing (2 ta belgidan iborat) mashinaga aylandi.
Vang / Post-Turing modeli bilan bog'liq qiyinchiliklar:
Muammo bundan mustasno: Vang modeli (7 ta yo'riqnomadan keyingi Turing mashinasining oltita ko'rsatmasi) hali ham bitta lentali Turingga o'xshash qurilma edi, ammo bu juda yaxshi ketma-ket dastur ko'rsatmasi-oqim bo'lishi mumkin. Ham Melzak (1961), ham Shepherdson va Sturgis (1963) buni kuzatdilar (ba'zi dalillar va tekshirishlar sharoitida):
"... Turing mashinasi ma'lum bir xiralashganlikka ega ... Turing mashinasi (gipotetik) ishda sust va odatda murakkab. Bu uni loyihalashni ancha qiyinlashtiradi va vaqt yoki saqlash kabi masalalarni o'rganishni qiyinlashtiradi. optimallashtirish yoki ikkita algoritm samaradorligini taqqoslash (Melzak (1961), 281-bet)
"... qiyin bo'lmasa-da ... dalillarni bajarish ikki sababga ko'ra murakkab va zerikarli: (1) Turing mashinasida faqat bosh bor, shunda hisoblashni bitta raqam bo'yicha operatsiyalarning juda kichik bosqichlariga ajratish kerak. . (2) Bitta lenta bor, shuning uchun birinchi raqamni ishlashni istash va uni boshqa raqamlardan ajratib olish uchun biron bir muammoga duch kelish kerak "(Shepherdson and Sturgis (1963) 218-bet).
Haqiqatan ham, misol sifatida Turing mashinasi misollari, Post-Turing mashinasi va qisman funktsiya ko'rsatish, ish "murakkab" bo'lishi mumkin.