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

Пост машинасына ұ қ сас, бірақ сә л басқ аша жұ мыс істейді. Тьюринг машинасы (ТМ) есепші таспадан (ұ яшық тарғ а бө лінген жә не солынан шектелген, бірақ оң ынан емес), оқ ып жә не жазатын тү біртектен, таспатартар механизм мен амал атқ арушы қ ұ рылғ ыдан тұ рады. Қ ұ рылғ ы кейбір ақ ырлы жиынғ а (ішкі кү й-жай ә ріппесіне) жататын дискретті кү йлерінің бірінде болады. Мұ ндағ ы - бастапқ ы кү й деп аталады.Оқ итын да, жазатын тү біртек жұ мысшы ә ріппесінің ә ріптерін оқ и да, ө шіре де, баспағ а шығ ара да алады. Таспаның ә рбір ұ яшығ ы ә р мезет А жиыны ә рпімен толтырылғ ан. -“бос орын” ә рпі бә рінен жиі кездеседі. Тү біртек ә р мезет таспа ұ яшығ ының бірі-ағ ымдағ ы жұ мысшы ұ яшық ү стінде тұ рады. Таспатар механизм тү біртек басының кө рші ұ яшығ ының ү стінде болатындай етіп таспаны жылжыта алады. Онда таспаның сол жақ шетіне шығ у жағ дайы болуы мү мкін. Ол жағ дай, тоқ тау туралы бұ йрық ты машинаның орындау барысындағ ы машиналық тоқ тау немесе апатты (болмайтын)тоқ тау болып табылады. ТМ жұ мыс реті (жұ мысшы ә ріппесі мен кү йлері бар). Тьюринг машинасы кестесі арқ ылы ө рнектеледі. Бұ л кесте тө рт тікжолды жә не (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) тұ ратын бастапқ ы конфигурацияның бірінен жұ мысын бастайды.

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