Kirish Roʻyxatdan oʻtish

Docx

  • Referatlar
  • Diplom ishlar
  • Boshqa
    • Slaydlar
    • Referatlar
    • Kurs ishlari
    • Diplom ishlar
    • Dissertatsiyalar
    • Dars ishlanmalar
    • Infografika
    • Kitoblar
    • Testlar

Dokument ma'lumotlari

Narxi 2000UZS
Hajmi 204.3KB
Xaridlar 0
Yuklab olingan sana 07 Noyabr 2026
Kengaytma docx
Bo'lim Referatlar
Fan Pedagogika

Sotuvchi

Bohodir Jalolov

Tyuring mashinasi

Sotib olish
Reja
1 Tyuring mashinasi.
2 Qurilma nimadan iborat.
3 Mexanizm xususiyatlari .
4 Qurilma dasturi.
5   Saqlangan dasturli kompyuter
6  Matematik nazariya.
7 Samaradorlik.
8 Ichki holatga ega bo'lmagan mashinalar
9 Adabiyotlar ro’yxati
Tyuring mashinasi Tyuring   mashinasi   20-asrning   eng   qiziqarli   va   hayajonli   intellektual   kashfiyotlaridan
biridir. Bu hisoblashning oddiy va foydali mavhum modeli (kompyuter va raqamli) bo'lib,
har   qanday   kompyuter   vazifasini   amalga   oshirish   uchun   etarlicha   umumiydir.
Rahmat   oddiy tavsif   va matematik tahlilni amalga oshirib, nazariy informatikaning asosini
tashkil   qiladi.   Ushbu   tadqiqot   raqamli   kompyuterlar   va   hisob-kitoblarni   chuqurroq
tushunishga   olib   keldi,   jumladan,   umumiy   foydalanuvchi   kompyuterlarida   hal
etilmaydigan ba'zi hisoblash muammolari mavjudligini tushunish.
BU NIMA VA KIM YARATGAN
Alan   Turing   kompyuter   bilan   bir   xil   asosiy   imkoniyatlarga   ega   bo'lgan   mexanik
qurilmaning   eng   ibtidoiy   modelini   tasvirlashga   harakat   qildi.   Turing   mashinani   birinchi
marta   1936   yilda   London   Matematik   Jamiyati   materiallarida   chop   etilgan   "Hisoblash
mumkin bo'lgan sonlar to'g'risida" gi masalani yechish muammosi bilan ta'riflagan.
Turing mashinasi - bu o'qish / yozish kallagidan (yoki "skaner") iborat bo'lgan hisoblash 
qurilmasi bo'lib, u orqali qog'oz tasmasi o'tadi. Lenta kvadratlarga bo'lingan, ularning har 
biri bitta belgi - "0" yoki "1". Mexanizmning maqsadi shundan iboratki, u ham kirish va  chiqish vositasi, ham hisob-kitoblarning oraliq bosqichlari natijalarini saqlash uchun ishchi
xotira sifatida ishlaydi.
QURILMA NIMADAN IBORAT
Har bir bunday mashina ikkita komponentdan iborat:
1. Cheksiz tasma. U har ikki yo'nalishda ham cheksiz bo'lib, hujayralarga bo'linadi.
2. Avtomatik mashina - boshqariladigan dastur, ma'lumotlarni o'qish va yozish uchun
bosh-skaner.  Bu har qanday vaqtda ko'plab shtatlardan birida bo'lishi mumkin.
Har bir mashina ikkita chekli ma'lumotlar qatorini bog'laydi: kiruvchi belgilar alifbosi A =
(a0,   a1,   ...,   am)   va   holatlar   alifbosi   Q   =   (q0,   q1,   ...,   qp).   q0   holati   passiv   deb   ataladi.
Taxminlarga ko'ra, qurilma urilganda o'z ishini tugatadi. q1 holati boshlang'ich holat deb
ataladi - mashina o'z hisob-kitoblarini uning boshida bo'lgan holda boshlaydi. Kirish so'zi
lentada joylashgan bo'lib, har bir pozitsiyada bir qatorda bitta harf. Uning ikkala tomonida
faqat bo'sh hujayralar joylashgan.
MEXANIZM QANDAY ISHLAYDI
Turing   mashinasi   hisoblash   qurilmalaridan   tubdan   farq   qiladi   -   uning   xotira   qurilmasi
cheksiz   lentaga   ega,   raqamli   qurilmalarda   esa   bunday   qurilma   ma'lum   uzunlikdagi
chiziqqa   ega.   Har   bir   vazifa   sinfi   faqat   bitta   qurilgan   Turing   mashinasi   tomonidan   hal
qilinadi. Boshqa turdagi muammolar yangi algoritm yozishni o'z ichiga oladi. Tekshirish   moslamasi   bitta   holatda   bo'lib,   kamar   bo'ylab   istalgan   yo'nalishda
harakatlanishi   mumkin.   U   chekli   alifboning   belgilarini   hujayralarga   yozadi   va   o'qiydi.
Harakat   paytida   bo'sh   element   tanlanadi,   u   kirish   ma'lumotlarini   o'z   ichiga   olmaydigan
pozitsiyalarni   to'ldiradi.   Tyuring   mashinasi   algoritmi   boshqaruv   qurilmasi   uchun   o'tish
qoidalarini   belgilaydi.   Ular   o'qish-yozish   boshiga   quyidagi   parametrlarni   o'rnatadilar:
katakka yangi belgi yozish, yangi holatga o'tish, lenta bo'ylab chapga yoki o'ngga siljitish.
MEXANIZM XUSUSIYATLARI
Tyuring mashinasi, boshqa hisoblash tizimlari kabi, o'ziga xos xususiyatlarga ega va ular
algoritmlarning xususiyatlariga o'xshaydi:
1. Diskretlik.   Raqamli   mashina   keyingi   bosqichga   o'tadi   n   +   1   oldingisi   tugagandan
keyingina.  Har bir tugallangan bosqich n + 1 bo'lishini belgilaydi.
2. Tushunuvchanlik.   Qurilma   bir   xil   hujayra   uchun   faqat   bitta   amalni   bajaradi.   U
alifbodagi belgini yozadi va bitta harakatni amalga oshiradi: chap yoki o'ng.
3. Determinizm.   Mexanizmdagi   har   bir   pozitsiya   ma'lum   bir   sxemani   bajarishning
yagona   variantiga   mos   keladi   va   har   bir   bosqichda   harakatlar   va   ularni   amalga
oshirish ketma-ketligi aniq. 4. Samaradorlik.   Har   bir   bosqich   uchun   aniq   natija   Turing   mashinasi   tomonidan
aniqlanadi.   Dastur   algoritmni   bajaradi   va   cheklangan   miqdordagi   qadamlarda   q0
holatiga o'tadi.
5. Ommaviy xarakter. Har bir qurilma to'g'ri alifbo so'zlari bo'yicha aniqlanadi.
TYURING MASHINASINING VAZIFALARI
Algoritmlarni   echishda   ko'pincha   funktsiyani   amalga   oshirish   talab   qilinadi.   Hisoblash
uchun   zanjirni   yozish   imkoniyatiga   qarab,   funktsiya   algoritmik   hal   qilinadigan   yoki   hal
etilmaydigan   deb   ataladi.   Tabiiy   yoki   ratsional   sonlar   to'plami   sifatida,   mashina   uchun
chekli N alifbosidagi so'zlar, biz B to'plamining ketma-ketligini ko'rib chiqamiz - B = (0,1)
ikkilik   kod   alifbosi   doirasidagi   so'zlar.   Shuningdek,   hisoblash   natijasi   algoritm   "osilib
qolganda" yuzaga keladigan "aniqlanmagan" qiymatni hisobga oladi. Funktsiyani amalga
oshirish   uchun   rasmiy   tilning   cheklangan   alifboda   mavjudligi   va   to'g'ri   tavsiflarni   tanib
olish muammosi hal qilinishi muhimdir.
QURILMA DASTURI
Turing mexanizmi uchun dasturlar jadvallar bilan formatlangan bo'lib, unda birinchi qator
va   ustun   tashqi   alifbo   belgilarini   va   mashinaning   mumkin   bo'lgan   ichki   holatining
qiymatlarini   -   ichki   alifboni   o'z   ichiga   oladi.   Jadvalli   ma'lumotlar   Turing   mashinasi
tomonidan   qabul   qilinadigan   buyruqlardir.   Muammolarning   yechimi   quyidagicha: hujayradagi   bosh   tomonidan   o'qilgan   xat,   u   yuqorida   joylashgan   bu   daqiqa   topiladi   va
mashina boshining ichki holati  buyruqlarning qaysi  biri bajarilishi  kerakligini  belgilaydi.
Xususan,  bunday  buyruq  jadvaldagi  tashqi   va  ichki   alifbo  belgilarining  kesishgan  joyida
joylashgan.
HISOBLASH KOMPONENTLARI
Bitta aniq muammoni hal qilish uchun Tyuring mashinasini qurish uchun uning quyidagi
parametrlarini aniqlash kerak.
Tashqi alifbo. Bu A belgisi bilan belgilanadigan, tashkil etuvchi elementlari harflar bilan
ataladigan ba'zi chekli belgilar to'plami. Ulardan biri - a0 - bo'sh bo'lishi kerak. Masalan,
Tyuring qurilmasi bilan ishlaydigan alifbo   ikkilik raqamlar , quyidagicha ko'rinadi: A = (0,
1, a0).
Lentaga yozib olingan harf-ramzlarning uzilmagan qatori so'z deyiladi.
Avtomat   -   bu   inson   aralashuvisiz   ishlaydigan   qurilma.   Turing   mashinasida   u
muammolarni hal qilish uchun bir necha xil holatlarga ega va yuzaga keladigan muayyan
sharoitlarda   bir   pozitsiyadan   ikkinchisiga   o'tadi.   Bunday   tashish   holatlarining   to'plami
ichki alifbodir. U Q = (q1, q2 ...) ko'rinishidagi harf belgisiga ega. Ushbu pozitsiyalardan biri   -   q1   -   boshlang'ich   bo'lishi   kerak,   ya'ni   dasturni   ishga   tushiradigan   narsa.   Yana   bir
zarur   element   -   bu   yakuniy,   ya'ni   dasturni   tugatuvchi   va   qurilmani   to'xtash   holatiga
keltiradigan holat q0.
O'tish stoli. Ushbu komponent mashinaning holati va hozirgi vaqtda o'qilayotgan belgining
qiymatiga qarab, qurilma vagonining xatti-harakati uchun algoritmdir. AVTOMAT UCHUN ALGORITM
Turing   qurilmasining   ish   paytida   tashish   dasturi   har   bir   bosqichda   quyidagi   harakatlar
ketma-ketligini bajaradigan dastur tomonidan boshqariladi:
1. Tashqi alifbo belgisini pozitsiyaga, shu jumladan bo'shga yozish, undagi elementni,
shu jumladan bo'shni almashtirish.
2. Bir katakchani chapga yoki o'ngga siljiting.
3. Sizning ichki holatingizni o'zgartirish.
Shunday   qilib,   har   bir   juft   belgilar   yoki   pozitsiyalar   uchun   dasturlarni   yozishda   uchta
parametrni   aniq tasvirlash  kerak:   ai  -  tanlangan  A  alifbosidan   element, vagonning  siljish
yo'nalishi ("←" chapga, "→" o'ng, "nuqta" - harakat yo'q) va qk - qurilmaning yangi holati
Masalan,  1 "←" q 2 buyrug'i  "belgini  1 ga almashtiring, vagon boshini  chapga bir  katak
qadamiga o'tkazing va bajaring. q 2" holatiga o'tish.
TYURING MASHINASI: MISOLLAR
1-misol.   Vazifa   lentada   joylashgan   berilgan   sonning   oxirgi   raqamiga   bitta   qo'shadigan
algoritmni qurishdir. Kirish ma'lumotlari - so'z - lentadagi ketma-ket hujayralarga yozilgan
butun   o'nli   raqamlar.   Dastlabki   vaqtda   qurilma   eng   o'ngdagi   belgi   -   raqam   raqamining
qarshisida joylashgan.
Yechim. Agar oxirgi raqam 9 bo'lsa, u 0 ga almashtirilishi kerak va keyin oldingi belgiga
qo'shilishi kerak. Bu holda dastur uchun   bu qurilma   Turingni quyidagicha yozish mumkin:
Bu   erda   q   1  -   raqam   o'zgarishi   holati,   q  0   -   to'xtash.   Agar   q  1   da  avtomat   0..8  qatordan
elementni tuzatsa, u holda uni mos ravishda 1..9 dan biri bilan almashtiradi va keyin q 0
holatiga o tadi, ya ni qurilma to xtaydi. Agar vagon 9 raqamini o'rnatsa, keyin uni 0 bilanʻ ʼ ʻ
almashtirsa,   keyin   q   1   holatida   to'xtab,   chapga   siljiydi.   Bu   harakat   qurilma   9   dan   kichik
raqamni   tuzatmaguncha   davom   etadi.   Agar   barcha   belgilar   9   ga   teng   bo‘lsa,   ular   nolga
almashtiriladi, yetakchi element o‘rniga 0 yoziladi, vagon chapga siljiydi va bo‘sh katakka
1 ni yozadi. . Keyingi qadam q 0 - to'xtash holatiga o'tish bo'ladi. 2-misol.   Sizga   ochiq   va   yopiq   qavslar   uchun   bir   qator   belgilar   beriladi.   Bir   juft   qavsni,
ya'ni bir qatorda joylashgan elementlarni - "()" olib tashlaydigan Turing qurilmasini qurish
talab   qilinadi.   Masalan,   boshlang'ich   ma'lumotlar:   ")   (()   (()",   javob   quyidagicha   bo'lishi
kerak:   ")..   ((".   Yechish:   q   1   da   bo'lgan   mexanizm,   chiziqning   eng   chap   elementini   tahlil
qiladi.
q   1   holati:   agar   “(”   belgisi   uchrasa,   o‘ngga   siljiting   va   q   2   holatiga   o‘ting;   agar   “a   0”
aniqlangan bo‘lsa, to‘xtating.
q 2  holat:  “(”  qavs  juftlik  mavjudligi   uchun tahlil   qilinadi, mos  kelsa,  “)”  bo'lishi   kerak.
Agar buyum juft bo'lsa, vagonni chapga qaytaring va q 3 ga o'ting.
q 3 holati: avval “(” va keyin “)” belgisini o‘chiring va q 1 ga o‘ting.
hozirda
Xozirgi zamon informatika fanining eng muhim savollaridan biri bu, uning yordamida har
qanday rasmiy ijrochiga taqlid qilish mumkin bo'lgan rasmiy ijrochining mavjudligidir. bu
savolga javobni deyarli bir vaqtning o'zida ikkita taniqli olim - A. Turing va E. Post oldi.
Ular taklif qilgan ijrochilar bir-biridan farq qilar edi, biroq ular bir-biriga taqlid qilishlari,
eng   muhimi,   har   qanday   rasmiy   ijrochining   ishiga   taqlid   qilishlari   mumkinligi   ma'lum
bo'ldi.
Rasmiy   pudratchi   nima?   Bu   nimani   anglatadi   -   bir   rasmiy   ijrochi   boshqa   rasmiy
ijrochining ishiga taqlid qiladimi? Agar o'ynagan bo'lsangiz   komputer o'yinlari - ekrandagi
ob'ektlar so'roqsiz o'yinchining buyruqlariga bo'ysunadi. Har bir ob'ekt  tegishli buyruqlar
to'plamiga   ega.   Shu   bilan   birga,   kompyuterning   o'zi   ijrochi   bo'lib,   virtual   emas,   balki
haqiqiydir. Shunday qilib, bir rasmiy ijrochi boshqa rasmiy ijrochining ishiga taqlid qiladi.
Turing mashinasi qanday ishlashini ko'rib chiqing. Tyuring mashinasi hujayralarga bo'lingan cheksiz lenta va lenta bo'ylab harakatlanadigan
karetka (o'quvchi-printer).
Shunday qilib, Tyuring mashinasi rasmiy ravishda ikkita alifbo to'plami bilan tavsiflanadi:
A = (a1, a2, a3, ..., an) - tashqi alifbo, dastlabki ma'lumotlarni yozish uchun ishlatiladi
Q   =   (q1,   q2,   q3,…,   qm)   -   ichki   alifbo,   o'quvchi   va   chop   etish   moslamasining   holatlar
to'plamini tavsiflaydi.
Lentaning har bir katakchasi tashqi alifbodan A = (a0, a1, ..., an) belgisini o'z ichiga olishi
mumkin (bizning holatda, A = (0, 1))
Tyuring mashinasining amaldagi harakatlari quyidagilardan iborat:
1)  tashqi   alifboning  istalgan   belgisini  lenta  katakchasiga   yozing  (ilgari   bo'lgan  belgining
ustiga yoziladi)
2) qo'shni katakka o'tish
3) holatni ichki Q alifbosi belgisi bilan ko'rsatilganlardan biriga o'zgartirish
Turing mashinasi - bu stol bilan boshqariladigan mashina.
Jadvaldagi qatorlar tanlangan A alifbosining belgilariga, ustunlar esa avtomat Q = (q0, q1,
…,   qm)   holatlariga   mos   keladi.   Ishning   boshida   Tyuring   mashinasi   q1   holatidadir.   q0
holati yakuniy holat bo'lib, unga kirgandan so'ng avtomat o'z ishini tugatadi.
Jadvalning   qandaydir   ai   belgisiga   va   qj   holatiga   mos   keladigan   har   bir   katakda   uch
qismdan   iborat   buyruq   mavjud
A   alifbosidagi   belgi
·   Harakat   yo'nalishi:   ">"   (o'ngga),   "<»   ( влево )   или   «.»   (на   месте)
Mashinaning yangi holati Yuqoridagi jadvalda A = (0, 1, _) alifbosi (3 ta belgidan iborat) va ichki alifbosi Q = (q1,
q2, q3, q4, q0), q0 - vagonning to'xtab qolishiga sabab bo'lgan holat.
Keling,   bir   nechta   vazifalarni   hal   qilish   orqali   ko'rib   chiqaylik.   Turing   mashinasini   veb-
saytning YUKLASH bo'limida yuklab olishingiz mumkin.
Masala 1. A = (0, 1, _) bo‘lsin. Lentada katakchalar alifbodan quyidagi tartibda joylashgan
belgilarni o'z ichiga oladi 0011011. Karet birinchi belgi ustida joylashgan. 0 ni 1 ga, 1 ni 0
ga almashtiradigan va karetani dastlabki holatiga qaytaradigan dastur yozish kerak.
Endi   vagonning   holatlarini   aniqlaymiz.   Men   ularni   "karetaning   biror   narsa   qilishni
istashlari" deb atayman.
q1)   Vagon   o‘ng   tomonga   ketishi   kerak:   agar   u   0   ni   ko‘rsa,   uni   1   ga   o‘zgartiradi   va   q1
holatda   qoladi,   1   ni   ko‘rsa,   0   ga   o‘zgartiradi   va   q1   holatda   qoladi,   agar   _   ni   ko‘rsa,   q1
holatda qoladi. orqaga ketadi 1 katak "boshqa narsani xohlaydi" , ya'ni q2 holatiga o'tadi.
Keling, o'z fikrimizni ijrochi jadvaliga yozamiz. Sintaksis uchun dastur yordamiga qarang)
q2)   Endi   biz   q2   “karetaning   xohishi”ni   tasvirlaymiz.   Biz   asl   pozitsiyamizga   qaytishimiz
kerak.   Buning   uchun:   agar   biz   1   ni   ko'rsak,   biz   uni   qoldiramiz   va   q2   holatida   qolamiz
(belgilar qatorining oxiriga etish istagi bilan); agar biz 0 ni ko'rsak, biz uni qoldiramiz va q2   holatida   chapga   o'tishni   davom   ettiramiz;   ko'ramiz   _   -   1   katakcha   o'ngga   siljiydi.
Muammo bayonotida talab qilinadigan joyda siz shu yerdasiz. q0 holatiga o'tamiz.
Masala   2.   Berilgan:   0   va   1   ning   yakuniy   ketma-ketligi   (001101011101).   Ularni   ushbu
ketma-ketlikdan keyin bo'sh katak orqali yozish kerak va bu ketma-ketlikda ularni 0 bilan
almashtirish kerak. Masalan:
001101011101 dan biz 000000000000 1111111 ni olamiz.
Ko'rib turganingizdek, bu  ketma-ketlikdan keyin  ettita birlik yoziladi   va ularning  o'rnida
nol bor.
Keling, mulohaza yuritishga o'taylik. Tashish uchun qanday holatlar va qancha kerakligini
aniqlang.
q1) arra 1 - uni nolga o'rnating va boshqa holatga o'ting q2 (vagon bir o'tishda hammasini
nolga o'zgartirmasligi uchun yangi holat kiritilgan)
q2) hech narsani o'zgartirmang, ketma-ketlikning oxiriga o'ting
q3)   karetka   bo‘sh   katakchani   ko‘rishi   bilan   o‘ngga   bir   qadam   tashlab,   bittasini   chizadi,
agar ko‘rsa, oxiridagi belgiga imzo qo‘yishga o‘tadi. Birlikni chizganimizdan so'ng, biz q4
holatiga o'tamiz
q4)   hech   narsani   o‘zgartirmagan   holda   yozma   birliklardan   o‘tamiz.   Ketma-ketlikni
birlikdan   ajratib   turuvchi   bo'sh   katakka   etib   borishimiz   bilan   biz   yangi   q5   holatidan
o'tamiz. q5)  bu holatda hech narsani  o‘zgartirmagan holda ketma-ketlikning boshiga o‘tamiz. Biz
bo'sh hujayraga etib boramiz, orqaga o'girilib, q1 holatiga boramiz
Karetaning   q1   holatida   shu   ketma-ketlikning   oxirigacha   o'tib,   bo'sh   katakka   duch
kelganida q0 holatini qabul qiladi.
Biz quyidagi dasturni olamiz:
BU NIMA?
"Tyuring   mashinasi"   simulyatori   -   universal   ijrochining   (mavhum   hisoblash   mashinasi)
o'quv   modeli   bo'lib,   1936   yilda   A.   Tyuring   tomonidan   algoritm   tushunchasini
aniqlashtirish uchun taklif qilingan.  Tyuring tezislariga ko'ra, har qanday algoritm Tyuring
mashinasi   uchun   dastur   sifatida   yozilishi   mumkin.   Tyuring   mashinasi   o'z   imkoniyatlari
bo'yicha Post mashinasi va oddiy Markov algoritmlariga teng ekanligi isbotlangan.
Tyuring mashinasi karetkadan (o'qish va yozish kallagi) va hujayralarga bo'lingan cheksiz
lentadan   iborat.   Lentaning   har   bir   katagida   A   =   (0,   1,...,   N)   alifbosidagi   belgi   bo'lishi
mumkin.   Har   qanday   alifboda   bo'sh   joy   mavjud   bo'lib,   u   0   yoki   l   bilan   belgilanadi.
Buyruqlarni kiritishda bo'sh joy pastki chiziq "_" bilan almashtiriladi. Turing mashinasi - bu stol bilan boshqariladigan mashina. Jadvaldagi qatorlar tanlangan A
alifbosining   belgilariga,   ustunlar   esa   avtomat   Q   =   (q   0,   q   1,…,   q   M)   holatlariga   mos
keladi.   Ishning   boshida   Tyuring   mashinasi   q   1   holatda   bo'ladi.   q   0   holati   yakuniy   holat:
unga kirgandan so'ng avtomat o'z ishini tugatadi.
Jadvalning   qaysidir   a   i   belgisiga   va   q   j   holatiga   mos   keladigan   har   bir   katakda   uchta
qismdan iborat buyruq mavjud:
1. A alifbosidagi belgi;
2. harakat yo'nalishi:> (o'ngda),
3. mashinaning yangi holati .
Saqlangan dasturli kompyuter
 
Devis      Turingning hozirda "saqlanadigan dastur kompyuteri" deb nomlanuvchi 
tushunchasi, "harakatlar jadvali" - mashina uchun ko'rsatmalarni kirish ma'lumotlari 
bilan bir xil "xotirada" joylashtirish haqidagi ishonarli dalillarni keltirib 
chiqaradi.   Jon fon Neyman    Amerikaning birinchi diskret-simvoli (analogdan farqli 
o'laroq) kompyuter haqidagi tushuncha   EDVAC    . Devisning 
so'zlari   Vaqt   "klaviaturani chertgan har bir kishi ... Turing mashinasining 
mujassamlashuvi ustida ishlaydi" va "Jon fon Neyman Alan Turing asari asosida 
qurilgan" (Davis 2000: 193 so'zlaridan iqtibos keltiradi).   Vaqt   1999 yil 29 martdagi 
jurnal).
Devis Turingning ishini aytadi   Avtomatik hisoblash mexanizmi      (ACE) kompyuter 
mikroprogramma tushunchalarini "kutgan" ( mikrokod    ) va   RISC      protsessorlar (Devis
2000: 188).   Knuth      Turingning ACE kompyuteridagi ishini "subroutine bilan 
bog'lanishni osonlashtiruvchi uskuna" ni loyihalashtirishga asoslaydi (Knuth 1973: 
225); Devis, shuningdek, bu ishni Turingning apparat "stek" dan foydalanishi deb 
ataydi (Devis 2000: 237 izoh 18). Turing mashinasi qurilishni rag'batlantirganidek   kompyuterlar    , UTM yangi 
boshlang'ich rivojlanishini rag'batlantirmoqda   kompyuter fanlari    . Dastlabki bo'lsa 
ham, birinchi bo'lib, montajchi "yosh o'q otadigan dasturchi" tomonidan EDVAC 
uchun taklif qilingan (Devis 2000: 192).  Fon Neymanning "birinchi jiddiy dasturi ... 
shunchaki ma'lumotlarni samarali saralash edi" (Devis 2000: 184). Knut, maxsus 
registrlarda emas, balki dasturning o'zida joylashtirilgan subroutine qaytishi fon 
Neyman va Goldstinga tegishli ekanligini kuzatadi. [4 ]   
  Knut bundan tashqari buni 
ta'kidlaydi
"Birinchi tarjima tartibi" Universal Turing Machine "deb aytilishi mumkin ... 
Oddiy ma'noda talqin qilish tartib-qoidalari Jon Mauchli tomonidan Mur 
maktabida 1946 yilda o'qigan ma'ruzalarida aytib o'tilgan edi ... Turing ham 
ushbu rivojlanishda ishtirok etdi; uning boshchiligida Pilot ACE 
kompyuterining izohlovchi tizimlari yozilgan "(Knuth 1973: 226).
Ma'lumot sifatida dastur tushunchasining natijasi sifatida Devis operatsion tizimlar 
va kompilyatorlarni qisqacha eslatib o'tadi (Davis 2000: 185).
Biroq, ba'zilari ushbu baho bilan bog'liq muammolarni tug'dirishi mumkin. O'sha 
paytda (1940-yillarning o'rtalaridan 50-yillarning o'rtalariga qadar) 
tadqiqotchilarning nisbatan kichik kadrlari yangi "raqamli kompyuterlar" 
me'morchiligi bilan chambarchas bog'liq edi.   Xao Vang      (1954), hozirgi vaqtda yosh 
tadqiqotchi quyidagi kuzatuvni o'tkazdi:
Turingning hisoblash funktsiyalari nazariyasi tezlashtirilgan, ammo raqamli 
kompyuterlarning keng miqyosli qurilishiga katta ta'sir ko'rsatmadi.  Nazariya 
va amaliyotning bu ikki jihati deyarli bir-biridan mustaqil ravishda ishlab 
chiqilgan. Asosiy sabab, shubhasiz, mantiqchilar amaliy matematiklar va 
elektrotexnika muhandislari qiziqtirgan savollardan tubdan farq qiladigan 
savollarga qiziqish bildirmoqda. Ammo, bir xil g'alati narsalarga duch 
kelmaslik mumkin emas, chunki ko'pincha bir xil tushunchalar ikki 
rivojlanishda juda boshqacha atamalar bilan ifodalanadi. "(Vang 1954, 1957: 
63) Vang uning qog'ozi "ikkita yondashuvni bog'laydi" deb umid qildi. Darhaqiqat, 
Minskiy buni tasdiqlaydi: "kompyuterga o'xshash modellarda Turing-mashina 
nazariyasining birinchi formulasi Vangda paydo bo'lgan (1957)" (Minsky 1967: 
200). Minskiy namoyishda davom etmoqda   Turing ekvivalenti      a   hisoblagich    .
Kompyuterlarning Turingning oddiy modellariga (va aksincha) qisqartirilishiga 
kelsak, Minskiy Vangni "birinchi formulani" yaratgan deb belgilashi munozara 
uchun ochiqdir. Minskiyning ham 1961 yildagi ham, Vangning ham 1957 yildagi 
maqolasi Shepherdson va Sturgis (1963) tomonidan keltirilgan bo'lsa-da, ular 
Evropa matematiklari Kafenst (1959), Ershov (1959) va Peter (1958) ning ishlarini 
keltiradi va qisqacha bayon qiladi. Matematiklar Germes (1954, 1955, 1961) va 
Kafenst (1959) ismlari Sheperdson-Sturgis (1963) va Elgot-Robinson (1961) ning 
bibliografiyalarida uchraydi. Yana ikkita muhim nom Kanadalik tadqiqotchilar 
Melzak (1961) va Lambek (1961). Ko'proq narsalarni ko'rish uchun   Turing 
mashinasi ekvivalentlari    ; ma'lumotnomalarni quyidagi manzilda topish 
mumkin   ro'yxatdan o'tish mashinasi    .
Matematik nazariya
Harakat jadvallarini satr sifatida kodlash bilan, asosan Turing mashinalarida boshqa 
Turing mashinalarining xatti-harakatlari to'g'risida savollarga javob berish mumkin 
bo'ladi. Biroq, bu savollarning aksariyati   hal qilib bo'lmaydigan    , ya'ni ko'rib 
chiqilayotgan funktsiyani mexanik ravishda hisoblash mumkin emasligini anglatadi. 
Masalan, ixtiyoriy Turing mashinasi ma'lum bir kirishda yoki barcha kirishlarda 
to'xtab qoladimi yoki yo'qligini aniqlash muammosi   Muammoni to'xtatish    , 
Turingning asl qog'ozida, umuman olganda, hal qilib bo'lmaydigan bo'lib 
ko'rsatilgan.   Rays teoremasi      Turing mashinasining chiqishi haqidagi har qanday 
ahamiyatsiz savol hal qilinmasligini ko'rsatadi.
Universal Turing mashinasi har qanday narsani hisoblashi mumkin   rekursiv 
funktsiya    , har qanday qaror   rekursiv til    va har qanday narsani qabul qiling   rekursiv  ravishda sanab o'tiladigan til    . Ga ko'ra   Cherkov-Turing tezisi    , universal Turing 
mashinasi tomonidan hal qilinadigan muammolar aynan an   algoritm      yoki 
an   samarali hisoblash usuli , ushbu atamalarning har qanday oqilona ta'rifi uchun. 
Shu sabablarga ko'ra universal Turing mashinasi hisoblash tizimlarini taqqoslash 
uchun standart bo'lib xizmat qiladi va universal Turing mashinasini simulyatsiya qila
oladigan tizim deyiladi   Turing tugadi    .
Universal Turing mashinasining mavhum versiyasi bu   universal funktsiya    , boshqa 
har qanday hisoblash funktsiyasini hisoblash uchun ishlatilishi mumkin bo'lgan 
hisoblanadigan funktsiya. The   UTM teoremasi      bunday funktsiya mavjudligini 
isbotlaydi.
Samaradorlik
 
Umumiylikni yo'qotmasdan Turing mashinasining kiritilishi alfavitda {0, 1} mavjud 
deb taxmin qilish mumkin; har qanday boshqa cheklangan alifbo {0, 1} orqali 
kodlanishi mumkin. Tyuring mashinasining harakati   M   uning o'tish funktsiyasi bilan 
belgilanadi. Ushbu funktsiyani {0, 1} alifbosi ustidagi satr sifatida ham osonlikcha 
kodlash mumkin. Alifbosining hajmi   M , unda tasmalar soni va holat oralig'ining 
kattaligi o'tish funktsiyasi jadvalidan chiqarilishi mumkin. Ajratilgan holatlar va 
belgilarni ularning pozitsiyalari bilan aniqlash mumkin, masalan. dastlabki ikkita 
holat konventsiya bo'yicha start va stop holatlari bo'lishi mumkin. Binobarin, har bir 
Turing mashinasi {0, 1} alifbosi ustidagi satr sifatida kodlanishi mumkin. Bundan 
tashqari, biz har bir yaroqsiz kodlash arzimas Turing mashinasiga zudlik bilan 
to'xtab turadigan xaritalarni va har bir Turing mashinasi, xuddi sharhlar singari, 
o'zboshimchalik bilan (masalan) 1 sonlar bilan to'ldirish orqali cheksiz ko'p 
kodlashlarga ega bo'lishiga chaqiramiz. dasturlash tilida ishlash. A mavjudligini 
hisobga olib, biz ushbu kodlashga erishishimiz ajablanarli emas   Gödel raqami      va 
Turing mashinalari orasidagi hisoblash tengligi va   m-rekursiv funktsiyalar    . Xuddi 
shunday, bizning qurilishimiz har bir ikkilik qator bilan bog'lanadi   a , Turing 
mashinasi   M
a . Yuqoridagi kodlashdan boshlab, 1966 yilda F. C. Xeni va   R. E. Stearns      Turing 
mashinasi berilganligini ko'rsatdi   M
a   bu kirishni to'xtatadi   x   ichida   N   qadamlar, 
keyin kirishlarni to'xtatadigan ko'p tarmoqli universal Turing mashinasi 
mavjud   a ,   x   (turli lentalarda berilgan) ichida   CN   jurnal   N , qayerda   C   kirish 
uzunligiga bog'liq bo'lmagan mashinaga xos doimiy   x , lekin bunga bog'liq   M ' s 
alifbosi hajmi, lenta soni va holatlar soni. Samarali ravishda bu     simulyatsiya, 
foydalanish   Donald Knuth    "s   Big O notation    . [5 ]   
  Vaqt murakkabligidan ko'ra kosmik 
murakkablik uchun mos keladigan natija shundan iboratki, biz maksimal darajada 
foydalanadigan tarzda taqlid qilishimiz mumkin   CN   hisoblashning istalgan 
bosqichidagi hujayralar, an     simulyatsiya.
Ichki holatga ega bo'lmagan mashinalar
Agar siz Turing mashinasida bir nechta kallalarga ruxsat bersangiz, unda ichki 
holatlarsiz Turing mashinasiga ega bo'lishingiz mumkin. Lentaning bir qismi sifatida
"holatlar" kodlangan. Masalan, 6 ta rangga ega lentani ko'rib chiqing: 0, 1, 2, 0A, 
1A, 2A. 0,0,1,2,2A, 0,2,1 kabi lentani ko'rib chiqing, bu erda 3 boshli Turing 
mashinasi uchlik ustida joylashgan (2,2A, 0). Keyin qoidalar har qanday uchlikni 
boshqa uchlikka o'zgartiradi va 3 boshni chapga yoki o'ngga siljitadi. Masalan, 
qoidalar (2,2A, 0) ni (2,1,0) ga o'zgartirib, boshni chapga siljitishi mumkin. Shunday
qilib, ushbu misolda mashina ichki holati A va B bo'lgan (harf bilan ifodalanmagan) 
3 rangli Turing mashinasi kabi ishlaydi. 2 boshli Turing mashinasi uchun ish juda 
o'xshash. Shunday qilib, 2 boshli Turing mashinasi 6 rangga ega universal bo'lishi 
mumkin. Ko'p boshli Turing mashinasi uchun zarur bo'lgan eng kichik ranglarning 
soni yoki bir nechta kallaklar bilan 2 rangli Universal Turing mashinasi mumkinligi 
ma'lum emas. Bu shuni ham anglatadi   qoidalarni qayta yozing      Turing to'liq, chunki 
uchta qoidalar qayta yozish qoidalariga teng. Lentani ikkita namuna olish uchun 
bosh va uning 8 ta qo'shnisi namuna oladi, faqat 2 ta rang kerak bo'ladi, masalan, 
rang 110 kabi vertikal uchlik shaklida kodlanishi mumkin.
Umumiy ma'lumotnomalar  Arora, Sanjeev; Barak, Boaz (2009).   Murakkablik nazariyasi: zamonaviy 
yondashuv    .  Kembrij universiteti matbuoti.   ISBN      978-0-521-42426-4    .   1.4 
bo'lim, "Iplar va universal Turing mashinalari kabi mashinalar" va 1.7, "1.9 
teoremasining isboti"
Adabiyotlar ro’yxati
1. Falina   I.N.   Maktab   informatika   kursida   "Tyuring   mashinasi"   mavzusi
(inf.1september.ru).
2. Mayer R.V.   Post va Turing mashinalari (komp-model.narod.ru).
3. Pilshikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V.   Tyuring mashinasi va
Markov   algoritmlari.   Muammoni   hal   qilish,   Moskva:   Moskva   davlat   universiteti,
2006 yil.
4. Bekman I.N.   Kompyuter fanlari. Ma'ruza 7. Algoritmlar (profbeckman.narod.ru)
5. A.   Formulalarsiz diskret matematika (lib.rus.ec)
6. Ershov   S.S.   Algoritmlar   nazariyasi   elementlari,   Chelyabinsk,   SUSU   nashriyot
markazi, 2009 yil.
7. Varpaxovskiy F.L.   Algoritmlar nazariyasi elementlari, M: Ta'lim, 1970.
8. Vereshchagin N.K., Shen A.   Hisoblash funktsiyalari, Moskva: MTsNMO, 1999 yil.
          9.   Martin Devis    ,   Umumjahon kompyuter: Leybnitsdan Turinggacha bo'lgan 
yo'l   (2017)
1. Arora va Barak, 2009, Teorema 1.9
2.          ^           Qalin harfli skriptni almashtirish. 1936 yil Turing, Devis 1965 yilda: 127–
128.  Turingning S.D tushunchasiga misol ushbu maqolaning oxirida 
keltirilgan. 3.          ^           Xususan: Burks, Goldstine, fon Neyman (1946),   Elektron hisoblash 
vositasining mantiqiy dizaynini oldindan muhokama qilish , Bell va Newell 
1971 yilda qayta nashr etilgan
4.          ^           Arora va Barak, 2009, Teorema 1.9
5.          ^           Arora va Barak, 2009 yil, 4.1-mashq
6.          ^           Rogojin, 1996 yil
7.          ^           Kudlek va Rogojin, 2002 yil
8.          ^           Neary and Woods, 2009 yil
9.          ^           Neary and Woods, 2009b
10.                    ^           "Shtetl-optimallashtirilgan» Blog arxivi »8000-chi band bo'lgan 
Beaver raqami ZF to'plam nazariyasidan chetda qoladi: Adam Yedidia va men
yangi maqola"    .   www.scottaaronson.com. Olingan   29 dekabr   2016.
11.                    ^           "Laconic - Esolang"    .   esolangs.org. Olingan   29 dekabr   2016.

Tyuring mashinasi

Sotib olish
  • O'xshash dokumentlar

  • Maktabgacha ta‘lim tashkilotida ovqatlanish ratsionini tashkil etish
  • Umumta‘lim maktablarida Imom Buxoriy hadislarini o‘rganishning ahamiyati
  • 2001-yil sentabr voqealri va uning xalqaro munosabatlarga
  • 1945-1990-yillarda Buyuk Britaniya
  • 1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi

Xaridni tasdiqlang

Ha Yo'q

© Copyright 2019-2026.

  • Balansdan chiqarish bo'yicha ko'rsatmalar
  • Biz bilan aloqa
  • Saytdan foydalanish yuriqnomasi
  • Fayl yuklash yuriqnomasi
  • Русский