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

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

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

7.1. сурет. Тьюринг машинасының схемасы.

Пост машинасындағыдай, лента жеке бөліктерге бөлінген, бірақ, Тьюринг машинасында головка қозғалмайды, ал лента оған қатысты оңға және солға қозғалады. Басқа айырмашылығы ол екілік алфавитте емес, кандай-да бір кез-келген A = { , a₁…a _n} шекті алфавитте жұмыс істейді – бұл алфавит сыртқы алфавит деп аталады. Онда бос белгі деп аталатын арнайы символы ерекшеленіп тұр, оны қандай-да бір ұяшыққа жіберу ондағы белгіні өшіріп, ұяшықты бос қалдырады. Лентаның әр ұяшығына бір ғана символ жазылады. Лентада сақталған ақпарат сыртқы алфавиттің бос белгісінен басқа белгілерінің шектелген тізбегімен бейнеленеді.

Головка әрқашан лента ұяшықтарының бірінің үстінде орналасады. Жұмыс тактілермен (қадамдармен) жүреді. Головкаларымен орындалатын командалар жүйесі қарапайым: әр такті сайын ол шолынулы ұяшықтағы a_i белгісін a_j белгісіне ауыстырады. Мұнда келесі сәйкестіктер болуы мүмкін:

• 
  j = i – бұл шолынулы ұяшықта ештеңе өзгермегенін білдіреді;
  
• 
  i 0, j = 0– ұяшықта сақтаулы белгі бос белгіге ауыстырылғанын, яғни өшірілгенін білдіреді;
  
• 
  i =0, j 0 - ұяшықта сақтаулы бос белгі бос емес белгіге (алфавиттегі j белгісіне) ауыстырылғанын білдіреді, яғни белгі қою орындалады;
  
• 
  i j 0 - бір белгіні екіншісімен ауыстыруды білдіреді.
  

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

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