«Информатиканың теориялық негіздері»

Тьюринг машинасында ақпаратты өңдеу және таңбаны жазу командасын беру, сол сияқты лентаны жылжыту логикалық құрылғы (ЛҚ) арқылы орындалады. ЛҚ шекті жиын құрып, Q ={q₁…q_m, z} арқылы бейнеленетін қалыптардың бірінде бола алады, z қалпы жұмыстың аяқталғанына сәйкес келеді, ал q₁ бастапқы қалып болып табылады. Q таңбасы R, L, S таңбаларымен бірге машинаның ішкі алфавтін құрады. ЛҚ екі кіру каналына (a_i, q_i) және үш шығу каналына (a_i+1, q_i+1, D_i+1) (суретке қара) ие:

Схеманы келесі түрде түсіну керек: i тактісінде ЛҚ-ның бір кірісіне сол мезетте шолынулы (a_i,) ұяшығынан белгі беріледі, басқа кірісіне сол мезеттегі ЛҚ-ның қалпын (q_i)-ді бейнелейтін белгі беріледі. Алынған (a_i, q_i) белгілерінің үйлесуіне және бар өңдеу ережелеріне байланысты ЛҚ жаңа (a_i+1) белгісін дайындап, бірінші шығыс каналынан шолынулы ұяшыққа бағыттайды, головканың орын ауыстыру командасын (R, L және S-ден D_i+1-ді) береді, сол сияқты келесі басқару белгісін (qi+1 ) шақыру командасын береді. Осылайша, Тьюринг машинасы жұмысының қарапайым қадамы (такт) келесіден тұрады: головка шолынулы ұяшықтан символды оқиды, және өзінің қалпына және оқылған символға байланысты қандай символ жазу (немесе өшіру) керектігі және қандай қозғалыс орындау керектігі жазылған команданы орындайды. Мұнда головка да жаңа қалыпқа өтеді. Мұндай машинаның функционалдану схемасы келесі 7.2 суретте көрсетілген.

Сурет 7.2. Тьюринг машинасының функционалдану схемасы

Осы схемада жадыны сыртқы және ішкі жадыға бөлу бейнеленген. Сыртқы жады шексіз лента түрінде көрсетілген – ол сыртқы алфавитттің символдарымен кодталған ақпаратты сақтауға арналған. Ішкі жады ағымдағы тактідегі келесі команданы сақтауға арналған екі ұяшық түрінде көрсетілген: Q-де ЛҚ-дан келесі қалып (q_i+1) беріліп, сақталады, ал D-да – жылжу командасы (D_i+1). Q-дан кері байланыс линиясы бойынша q_i+1 ЛҚ-ға түседі, ал D-дан команда қажет кезінде лентаны бір позиция оңға немесе солға жылжытатын орындаушы механизмге түседі.

Тьюринг машинасы жұмыс істейтін жалпы ережені келесі жазба түрінде көрсетуге болады: q_ia_j q_i’a_j ’D_k, яғни, q_i қалпында головканың a_j символын шолуынан кейін ұяшыққа a_j’ символын жазады, головка q_i’ қалпына өтеді, ал лента D_k жылжуын жасайды. Әрбір q_ia_j комбинациясы үшін тура бір түрлендіру ережесі бар (ереже тек қана z үшін жоқ, себебі бұл қалыпқа түскенде машина тоқтайды). Бұл логикалық блоктың мынадай функцияны жүзеге асыратынын білдіреді: әрбір q_ia_j қос кіру синалына бір және тек бір q_i’a_j’D_k үштік сигналын сәйкестендіреді – бұл машинаның логикалық функциясы деп аталып, әдетте кесте (машинаның функционалды схемасы) түрінде көрсетіледі, олардың бағандары қалыптардың символдарымен белгіленеді, ал жолдары сыртқы алфавит белгілерімен бейнеледнеді. Егер сыртқы алфавит таңбалары n, ал ЛҚ-ның қалыптарының саны m болса, онда түрлендіру ережелерінің жалпы саны n ·m болады.

Нақты Тьюринг машинасы A и Q жиындарының элементтерін көрсетумен, және сол сияқты ЛҚ-ны жүзеге асыратын логикалық функциялармен , яғни түрлендіру ережелерінің жиынтығымен беріледі. Әртүрлі A, Q жиындары мен логикалық функциялар шексіз көп болатыны түсінікті, яғни Тьюринг машинасы да сол сияқты шексіз көп.

Тьюринг машинасының функционалдануын талдамас бұрын тағы бір ұғым енгізейік.