Tyuring mashinalari

Tyuring mashinalari Reja : Tyuring mashinasi. Tyuring mashinasining xarakterli =ismlari. Tyuring mashinasining dasturi. Misollar. Adabiyotlar : [ 1 ], Y bob, 3,4 -§§. Tyuring mashinasi abstrakt mashina bilib uning shisoblash =obiliyati shunchalik yu=oriki, u ixtiyoriy matematik algoritmni realizatsiya =ilishi mumkin. Tyuring mashinasi ikkala tomonga ixtiyoriy davom ettirish mumkin bilgan va teng katakcha (yacheyka)larga bilingan lentadan shamda lenta biylab diskret harakat =iladigan karetka (shisoblovchi =urilma)dan iboratdir. S s1, . . . , sm , m 1 - tash=i alfavit , S' s0, s1, . . . , sm - kengaytirilgan tash=i alfavit. Bu yerda s0 - bish katakni anglatadi. S tiplam elementlari tash=i alfavitning aktiv simvollari deyiladi. «Ichki alfavit» - Q q0, . . . , qk- chekli tiplam elementlari Tyuring mashinasining ichki sholatlari deyiladi. Bunda q1- Tyuing mashinasining boshlanich, q0- oxirgi sholati. q1,q2, . . . , qk - lar aktiv ichki sholatlar deyiladi. Tyuring mashinasining q0 - ichki sholatda bilishi uning ishdan tixtaganligini bildiradi. Q tiplam Tyuring mashinasining «ichki xotirasi» deb sham yuritiladi. Ish jarayonida Tyuring mashinasi bir ichki sholatdan bosh=a ichki sholatga itishi va lentaga S' alfavit elementlarini yozishi mumkin. Tyuring mashinasi lentasining shar bir katakchasi chekli sholatda biladi, yani katakcha yoki bish (s0), yoki si (i 1, . . . ,m) yozilgan bilishi mumkin. Tyuring mashinasi =uyidagi ishlarni bajarishi mumkin: Karetka lenta biylab shar bir va=t davomida bitta katak chapga yoki bitta katak ingga siljishi mumkin yoki iz irnida turishi mumkin. Karetka lenta ustidagi simvollarni izgartirishi mumkin, yani lentaga yozilgan simvolni ichirishi, uning irniga bosh=a simvolni yozishi mumkin, bish katakka aktiv simvollardan yozishi va shokazo. Щar bir Tyuring mashinasi iz dasturiga ega bilib, u ana shu dastur asosida ishlaydi. Dastur =uyidagi jadvaldan iborat : s0 s1 . . . st . . . sm q1 . . . . . . . . . . . . . . . . . . qj sjRqi . . . . . . . . . . . qk . . . . . . Jadvalni tashkil etgan kataklarda ish davomida bajariladigan komandalar yozilgan biladi, shar bir komanda sjRqi kirinishda bilib, bunda R bilan P, L, N (mos ravishda «ing», «chap», «joyida» sizlarini bildiradi) belgilarning biri belgilangandir : P, L belgilari mos ravishda karetkaning ingga yoki chapga surilishini, N esa karetka lenta biylab iz sholatini sa=laganini bildiradi. Tyuring mashinasi diskret rejimda (=adam-ba=adam) ishlaydi: u shar bir va=t momenti oraliida fa=at bitta komandani bajaradi. Tyuring ...