Тьюринг машинасы

Ағылшын математигі А. Тьюринг (1912-1954 ж.ж.) 1936 ж. ойлап тауып, ал 1937 ж. бір жұмысын жарыққа шығарды. Онда ол алгоритм түсінігін қазіргі кезде Тьюринг машинасы деп аталатын абстракт есепші машинаның көмегімен нақтылаған. Әр Тьюринг машинасында келесі үш бөлік бар: 1) сыртқы есте сақтағыш; 2) санап жазатын құрал; 3) басқаратын құрал.

Сыртқы есте сақтағыш екі жағынанда шектелмеген және өзара бірдей ұяшықтарға бөлінген лента.

Санап жазатын құрал – аңық бір уақытта қандайда бір ұяшыққа қарсы орналасатың құрал. Басқаратын құрал санап жазатын құралға түсетін бұйрықтарды дайындайды.Сонымен қатар басқаратын құралға санап жазатын құралдан қарсы орналасқан ұяшықтын символы келіп түседі.

Конфигурация деп ұяшықтардын символдар a_i1, a_i2, ..., a_ir, тізбегінен ішкі күйдің q_j символынан және санап жазатын құралға сәйкес тұрған ұяшықтын k нөмерінен құрылған жиынды атаймыз. Бұл берілгендер машина сөзі түрінде былай жазылады a_i1, a_i2 , ..., a_ik-1, q_j, a_ik, ..., a_ir.

Тъюринг машинасы орындайтын барлық бұйрықтарды оның бағдарламасы деп атаймыз.

Тюринг машинасын алгоритмдік үрдістерді сипаттау формализациясымен танысу құралы ретінде қарастырамыз. Тюринг машинасы екі жағынанда шексіз ленталармен жұмыс жасайды. Лента ұяшықтарға бөлінген, олардың жиынтығы машина жадын құрайды. Жадтың әрбір ұяшығы машинаның сыртқы алфавитін құратын алдын-ала фиксерленген символдар жиынтығы ішінен тек бір ғана символды сақтай алады.

S_{0 ,}S_1, S_2..., сыртқы алфавит символдарының ішінде ерекше бір символ бар бұл бос ˆ белгісімен белгіленеді. ˆбелгілерінен тұратын жад ұяшығын бос ұяшық деп атайды. Шексіз лентада орналасатын жадтан басқа машинаның бас ұшы деп аталатын арнайы құрылғы бар. Бас ұшы лента бойын жағалай орын ауыстыра алады. Бас ұшы көмегімен машина шолып шыққан ұяшықтың ішіндегісін оқи алады.

Машинасы жұмысы жеке такті ретінде құрайды. Олардың жүрісі барысында бастапқы ақпараттың қандайда бір ақырлы ақпаратты түрлендірілуі жүзеге асады.

S0

S1

….

Si

….

Sn

1 сурет - Машина конфигурациясының сызбасы

Мұндағы машинаның ішкі күйі q_k дәл сол уақыттағы шолып шыққан және S_і символынан тұратын ұяшық астында орналасқан. Машина жұмысының әрбір тактісінде:

1. Жадының шолып шыққан ұяшығында S_і символын оқиды.

2. Жадының шолып шыққан ұяшығына S_і сыртқы алфавитінің қандай да бір символын жазады.

3. Бас ұшын бір ұяшыққа не оңға не солға жылжытады немесе сол орнында қалтырады.

4. Қандай да бір q_і ішкі күйге көшеді.

Тюринг машинасына мысал: Тюринг машинасы қарапайым болғанымен сөздердің әр түрлі түрлендірілуін орындай отыра әр түрлі алгоритмдерді жүзеге асырады.

Тапсырма 1.

Лентадағы санға бірді қосып отыратын Тюринг машинасын құру керек. Ішкі сөз бүтін ондық сандар цифрінен тұратын лентаның тізбектелген ұяшықтарында орналасқан. Бастапқы мезетте машина санның ең соңғы оң жағында цифріне қарсы орналасқан.

Шешімі: Машина санның соңғы цифріне 1-ді қосып отыру керек, егерде соңғы цифр 9-ға тең болса,онда оны 0-мен ауыстырып 1- ді оның алдындағы цифрге қосу керек. Мұндай цифрлар Тьюринг машинасына арналған кесте төмендегідей болуы мүмкін:

	S0	0	1	2	3	4	….	7	8	9
Q1	1Hq0	1Hq0	2Hq0	3Hq0	4Hq0	5Hq0	….	8Hq0	9Hq0	0Hq0

Бұл Тьюринг машинасында q₁- цикл күйінің өзгеруі, q₀ күйі тоқтату күйі. Егер автомат 0 – ден 8- ге дейінгі цифрларды көрсе онда оларды сәйкесінше 1 –ден 9 ға дейін өзгереді және q₀ күйге көшеді. Егер де оны 9 цифрін көрсе онда оны 0 - мен ауыстырып, q₁ күйінде қала отырып солға жылжиды. Бұл процессте автомат 9-дан кіші цифрді кездестіргенше жалғасады. Егер барлық цифрлар 9-ға тең болса, онда барлығы 0- мен ауыстырылады, сонымен үлкен цифрі орнына үлкен цифрді жаза отырып , солға жылжып бос ұяшыққа 1-ді жазады, содан соң q₀ күйге көшеді, яғни тоқтайды. Тюринг машинасын жазуды қысқарту, яғни тоқтату күйіне көшуді «!» белгісімен белгілейді. Ол мынадай түрге келеді:

	S0	0	1	2	3	4	….	7	8	9
Q1	1H!	1H!	2H!	3H!	4H!	5H!	….	8H!	9H!	0H!

Тьюринг тезисі алгоритмдер теориясындағы Тьюринг түрінде берілген негізгі гипотеза болып табылады. Бұл тезис алгоритмнің формальды анықтамасын беруге мүмкіндік береді.

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

Черч тезисі. Алгоритмнің кез келген формализациясын алгоритмнің дәл анықтамасы екенін дәлелдеу мүмкін емес. Оны не қабылдауға,не қабылдамауға болады. Тьюрингтен бөлек математиктер де есептеуге болатын функциялардың анықтамаларын берді. Дегенімен, олардың барлығы Тьюринг анықтамасымен эквивалент болып шықты. Есімізге Клини, Пост, Марковтардың анықтауларын алсақ та жеткілікті. Сондықтан, осы формализациялардың кез келгенін алгоритмнің дәл анықтамасы ретінде алуға болады деп есептелінеді. Бұл ойды Черч айтқан болатын. Ол екі тезисті ұсынды:

1-Черч тезисі. Есептеуге болатын функциялар жиыны Тьюринг машинасында есептелінетін функциялар жиынына тең.

2-Черч тезисі. Алгоритмі бар функцияны есептейтін Тьюринг машинасы бар.

Бұл эквивалент екі тезистің ешқайсысын дәлелдеу мүмкін емес. Себебі, ол үшін алгоритмнің дәл анықтамасы керек. Бұл тезиске келіспеген математиктердің Тюринг машинасы есептемейтін алгоритм табуға тырысқан еңбектерінен ештеңе шықпады. Сондықтан, қазіргі заманда Черч тезисімен келіспеген математиктер қалмады деуге болады.

Кейбір Тьюринг машиналары кейбір мәндерінде тоқтамауын байқау қиын емес. Сондықтан, Тьюринг машинасымен есептелетін функцияларды кейде жартылай рекурсивті функция деп атайды, кейде рекурсивті функция деп атайды. 

Енді Черч тезисінен шығатын бірнеше теоремаларға тоқтала кетейік.

Теорема 1. Жартылай рекурсивті функциялар жиыны саналымды.

Дәлелдеуі. Черч тезисі бойынша f(х) =k функциясы кез келген k үшін рекурсивті. Сондықтан, жартылай рекурсивті функциялар кем дегенде саналымды.

Анықтама. Кез келген мәнінде анықталған жартылай рекурсивті функция жалпы рекурсивті функция деп аталады.

Салдар. Жалпы рекурсивті функциялар саналымды.

Дәлелдеуі. f(х) = k функциясы кез келген k үшін анықталған. Сондықтан, олар кем дегенде саналымды. Екінші жағынан, жалпы рекурсивті функциялар жиыны жартылай рекурсивті  функциялар жиынының ішкі жиыны болғандықтан саналымдыдан артық емес.