5. Тьюринг машинасы. Жұмыс істеу алгоритмі.

Пост машинасына ұқсас, бірақ сәл басқаша жұмыс істейді. Тьюринг машинасы (ТМ) есепші таспадан (ұяшықтарға бөлінген және солынан шектелген, бірақ оңынан емес), оқып және жазатын түбіртектен, таспатартар механизм мен амал атқарушы құрылғыдан тұрады. Құрылғы кейбір ақырлы жиынға (ішкі күй-жай әріппесіне) жататын дискретті күйлерінің бірінде болады. Мұндағы - бастапқы күй деп аталады.Оқитын да, жазатын түбіртек жұмысшы әріппесінің әріптерін оқи да, өшіре де, баспаға шығара да алады. Таспаның әрбір ұяшығы әр мезет А жиыны әрпімен толтырылған. -“бос орын” әрпі бәрінен жиі кездеседі. Түбіртек әр мезет таспа ұяшығының бірі-ағымдағы жұмысшы ұяшық үстінде тұрады. Таспатар механизм түбіртек басының көрші ұяшығының үстінде болатындай етіп таспаны жылжыта алады. Онда таспаның сол жақ шетіне шығу жағдайы болуы мүмкін. Ол жағдай, тоқтау туралы бұйрықты машинаның орындау барысындағы машиналық тоқтау немесе апатты (болмайтын)тоқтау болып табылады. ТМ жұмыс реті ( жұмысшы әріппесі мен күйлері бар). Тьюринг машинасы кестесі арқылы өрнектеледі. Бұл кесте төрт тікжолды және (s+1) (t+1) жолы бар матрица болып табылады. Әр жол мына түрде болады Мұнда арқылы әріппесі мен таспатартар механизм үшін бүйрықтар жиынын біріктіру элементі белгіленген. Бұйрықтар жиыны: l-таспаны солға орналастыру, r-таспаны оңға орналастыру, s-машинаны тоқтату; vіj –a0, a1,...., at әріппесі таңбасын таспа ұяшығына жазудан, не түбіртекті қозғаудан, не машинаны тоқтатудан тұратын ТМ әрекеті; qіj келесі күй-жай болып табылады. ТМ мына ережелер бойынша жұмыс істейді:

 

Егер ТМ qі күйінде болса, түбіртек жұмысшы ұяшығынан aj таңбасын оқиды. qі aj таңбаларынан басталатын qі aj vіj qіj жолы кестеде бір-ақ рет кездеседі. Егер vіj- жұмысшы әріппесінің әрпі болса, онда түбіртек жұмысшы ұяшықтағыны өшіріп, оған осы әріпті апарып жазады. Егер vіj- таспатартар механизм үшін r немесе l командасы болса, онда таспа оңға немесе солға бір ұяшыққа жылжиды (егер таспаның сол жақ шетіне шығып кетпесе).Тюринг машинасы А әріппесінің бір таңбасы бар таспаның белгілі ұяшығы үстін оқып-жазатын түбіртектің орны мен бастапқы күйден (әдетте q0) тұратын бастапқы конфигурацияның бірінен жұмысын бастайды.

ТМ жұмысшы әріппесінде әртүрлі таңбалардың болуы таспада кезкелген мәтіндік және сандық ақпаратты көрсетуге мүмкіндік береді, ал ТМ басқару орталығының әртүрлі күйге ауысуы Тюринг машинасының жұмыстың аралық нәтижелерін жадында ұстауын модельдейді. ТМ жұмысы ретін анықтайтын кесте тура мағынада программа емес (оның бұйрықтары кезекпен бірінен соң бірі орындалмайды, таспадағы әлдебір мәтіннің таңбаларын түрлендіруді өрнектейді). ТМ кестесін жиі Тюринг машинасының сүлбесі деп атайды немесе ТМ құрылысы мен жұмыс істеу негізі белгілі болғандықтан Тюринг машинасының өзімен теңдестіре салады.

 

Машинаның жұмыс істеу ережелері

 

Машина дискретті түрде жұмыс істейді (қадам қадам бойынша). Әр қадамда бір конфигурациядан басқасына өту орындалады. Жұмыс бастаудан алдын машина бастапқы конфигурацияда болады: оқып-жазушы құрылғы сөздің бірінші әріпіне шолу жасайды, ал машина q₁ бастапқы жағдайында болады_. Оқып-жазушы құрылғы шолу жасалған ұяшықтағы әріпті оқиды. Басқару құрылғысы машинаның программасынан оқылған әріп пен машинаның жағдайына сәйкес клетканы табады. Бұл клеткада (а, q, s) үштік болсын. Онда шолу жасалған ұяшыққа а әріпі жазылады, машина q жағдайға өткізіледі, егер s=-1 болса, онда оқып-жазушы құрылғы бір ұяшыққа сол жаққа жылжыйды, егер s=+1 болса, онда оқып-жазушы құрылғы бір ұяшыққа оң жаққа жылжыйды, егер s=0 болса – қозғалмайды. Осымен машинаның бірінші қадамдағы жұмысы аяқталады.

Машинаның жұмыстары машинаның қадамы q₀ ға жеткенше жалғаса береді. Бұл жағдайда басқару құрылғысы машинаны тоқтатады. Пайда болған конфигурацияқорытынды, ал алынған сөз – машинаны берілген сөзге қолдану нәтижесі деп аталады.