«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina.»


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



Download 52,14 Kb.
bet6/13
Sana30.04.2022
Hajmi52,14 Kb.
#597950
1   2   3   4   5   6   7   8   9   ...   13
Bog'liq
«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina (1)

(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.

Download 52,14 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   13




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish