Тьюринг машинасы. Тьюринг машинасы - құрылымына бос немесе белгіленген алфавиттің символы бар ұяшықтарға бөлінген шексіз таспамен әрекеттесетін шектеулі анықталған автомат кіретін абстракты автомат

Тьюринг машинасы. Тьюринг машинасы - құрылымына бос немесе белгіленген алфавиттің символы бар ұяшықтарға бөлінген шексіз таспамен әрекеттесетін шектеулі анықталған автомат кіретін абстракты автомат.

Тьюринг машинасы Пост машинасына ұқсас, бірақ басқаша жұмыс істейді.

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

Оқылатын және жазылатын бүркеншік A = {a₀, a₁, ..., a_t} жұмыс әліпбидің әріптерін оқи алады, оларды өшіре және басып шығара алады. Таспаның әрбір ұяшығы әрбір уақыт мезетте А жиынның әріптерімен бос емес. Жиі a₀ – «бос орын» әріпі кездеседі. Бүркеншік әрбір уақыт мезетте таспаның кейбір ұяшығының үстінде – ағымдағы жұмыс ұяшығында орналасады. Таспа созылынқы механизмі бүркеншік таспаның көршілес ұяшығының үстінде болатындай етіп таспаны ауыстыра алады. Бұл кезде таспаның сол жақ шетіне (СЖШ) шығып кетуі мүмкін, оны авариялық (жарамсыз), немесе машина тоқтату туралы ұйғарымды орындайтын машинналық тоқтату (МТ) болып табылады.

ТМ жұмыс реті (a₀, a₁,..., a_t жұмыс әліпебимен және q₀, q₁,..., q_s қалып-күйлерімен) Тьюринг машинасының кестесімен түсіндіріледі. Бұл кесте төрт бағанасы және (s + 1)(t + 1) жолы бар матрица. Әрбір жолдың келесі түрі бар

q_i a_j v_ij q_ij, 0 £ i £ s, 0 £ j £ t, q_ij Î {q₀, q₁,..., q_s}.

Мұнда v_ij арқылы {a₀, a₁, ..., a_t} әліпби біріктіру элементі мен таспа созылынқы механизм үшін ұйғарымдар жиыны Л – таспаны сол жаққа қарай ауыстыру, П – таспаны он жаққа қарай ауыстыру, С – машинаны тоқтату (ТОҚТА) белгіленген; v_ij –ұяшыққа a₀, a₁, ..., a_t әліпбидің таспа символын енгізуден, бүркеншітін жылжуынан, машина тоқтауынан тұратын ТМ-ның әрекеті; q_ij келесі қалып-күй болады.

ТМ келесі ережелерге сәйкес жұмыс істейді: егер ТМ q_i қалып-күйде болса, бүркеншік жұмыс торында a_j символын оқиды. Кестеде q_i a_j символдарынан басталатын q_i a_j v_ij q_ij жол бір рет кездеседі дейік. Егер v_ij – жұмыс әліпбидің әріпі болса, онда бүркеншік жұмыс ұяшығының ішіндегісін өшіріп, онда осы әріпті енгізеді. Егер v_ij –таспа созылынқы механизм үшін r немесе l командасы болса, онда лента оң жаққа қарай немесе сол жаққа қарай бір ұяшыққа жылжытылады (егер таспаның сол жақ шетіне шығып кетпесе). Егер v_ij = s, онда машиналық тоқтату болады.

Тьюринг машинасы өз жұмысын кейбір бастапқы сырт пішінінен бастайды. Ол өзіне А жұмыс әліпбидің бір символын қамтитын бастапқы жағдай (q₀) мен таспаның нақты ұяшығының үстіндегі оқып-жазатын бүркеншіктің орналасуынан тұрады.

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

Тьюринг машинасының схемасы — ағымдағы әрекетке тәуелді Тьюринг машинасының барлық мүмкін болатын қадамын санау (ақырғы емес қалып-қүй, қабылданатын символ). Комбинация, әдетте, екі кірісі бар кесте түрінде беріледі, кестенің тор көзінде Тьюринг машинасы қадамының коды (машинаның командалары) болады.

Тьюринг машинасының схемасы мысалын қарастырайық. Ондық санау жүйесіндегі n санына бірлікті қосу алгоритмі.

Айқын, ТМ-ның сыртқы әліпбиі 0,1,2,3,4,5,6,7,8,9 он цифрдан және бос орын_ символынан тұру керек. Бұл цифрларды ұяшыққа бір бірден жазады (қатар, қалдырусыз).

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

1) әртүрлі символдар әртүрлі кодтық топтарымен ауыстырылуы керек, бірақ бірдей символ қай жерде кездессе де, сол кодтық топпен ауыстырылуы қажет;

2) кодтық жазулардың жолдары жеке кодтық топтарға бөлінуі керек;

3) Л, П, С командаларына сәйкес келетін кодтық топтарды тануға, сыртқы әліпбидің символдары мен ішкі қалып-күйлеріне сәйкес келетін кодтық топтарды айыра білуге мүмкіншілік болу керек.