5	0	1	#
з	з, 0,К	з, 1,К	я, #,Ь
я	Я/, 1,ь	Я, 0,ь	Я/, 1,ь

Проаналізуйте роботу мт на наступних вхідних словах:

а) 00; в) 10011;

б) 100; г) 111.

Після цього, вважаючи вхідні слова записами натуральних чи­сел в двійковій системі числення, постарайтесь побачити загальну закономірність роботи машини на усіх вхідних словах.

1.5. Нехай МТ зображена графом:

а/Ь;Н Ь/а;Н

Задайте її як п'ятірку МТ = (Я, А,5, з, ду) та визначте мову, що розпізнається даною МТ.

6. Знайти мову, що породжується машиною Тюрінґа з попере­днього прикладу.

7. Побудувати граф та проаналізувати роботу машини Тюрінґа МТ = (Я, А, 5, з, ду) на словах 1^п = де Я = {з,ді,д₂,Яу},

п

А = {0,1, #}, а програма роботи 5 задана у вигляді таблиці:

5	0	1	#
з	Я2, 1,Я	Яі, #,Я	Я2, 1,Я
Яі	Я2, 1,Я	яу, #,Я	Я2, #,Я
Я2	Я2, 1,Я	Я2, 1,Я	Я2, 1,Я

Як працює машина на слові 1000000? Яку мову розпізнає дана МТ?

1.8. В чому полягає робота машини Тюрінґа МТ = (Я, А, 5, з, ду), де Я = {з, д₁, д₂, дз, Яу}, А = {а, Ь, #}, а програма роботи 5 задана у вигляді таблиці:

5	а	Ь	#
з	д1 ,а, Я	Я2, Ь, Я
Яі	д1 ,а, Я	д2, а, Я	Яз, #,Ь
Я2	д1 ,а, Я	Я2, Ь, Я	Яз, #,Ь
Яз	ду, а, Я	Яу, Ф,ь

1.9. Знайти мову, яку розпізнає МТ, задана графом.

0/0,Ь/Ь;П 0/0,Ь/Ь;Ь

б)

0/0,1/1;П

О*

#/#\Ь

#/#\Ь

0/0,1/1;П

Лекція 2. Алгоритми синтезу МТ

Розглядаються задачі на складання алгоритмів для МТ, на при­кладах пояснюються основні прийоми складання таких алгоритмів.

2.1. Приклад. Побудувати машину Тюрінґа, яка застосовна до всіх слів в алфавіті X = {а,Ь} і видаляє із вхідного слова його останню букву.

а/а,Ь/Ь;Н

Для розв'язання цієї задачі потрібно перемістити головку МТ під останню букву і стерти її. Нехай з - стан, в якому головка МТ пе­реміщується під останню букву слова. Для цього керуючий пристрій МТ переміщує головку комірка за коміркою праворуч, не міняючи букви і залишаючись в стані з. Але тут виникає невелика проблема: МТ бачить тільки активну комірку і не може визначити чи наступна комірка порожня чи ні. Тому головка МТ спершу переміщується під першу порожню комірку (в ній записаний символ #), яка розміще­на після вхідного слова, а потім керуючий пристрій, перебуваючи в стані з і аналізуючи символ # переходить в новий стан д₁, в якому стирає останню букву і зупиняє свою роботу (переходить в кінцевий стан д^). Таким чином, граф МТ буде мати наступний вигляд.

^а,Ь/#

Проаналізуємо роботу даної МТ на вхідних словах аЬЬ, а і е. (з, аЬЬ) ^ (з, аЬЬ) ^ (з, аЬЬ) ^ (з,аЬЬ#) ^ (д₁ ,аЬЬ) ^ (д/,аЬ). ^(з,а⁾ ^ ^(з,а#⁾ ^ ^,а⁾ ^ ⁽Я.ї^, #⁾. (з, #) ^ (91, #) ^ ...

Ми бачимо, що на порожньому слові робота МТ невизначена і дана МТ не розпізнає порожнього слова. В зв'язку з цим домовимо­ся, що порожнє слово МТ не змінює. Остаточно, граф МТ матиме вигляд.

а/а,Ь/Ь;Н

^ (£) ^ і

Таким чином, МТ задається як п'ятірка МТ = А, 5, з, д/), де Я = {з,Я₁ ,Я/}, А = {а,Ь, #}, X = У = {а, Ь}, Б = {#}, і програма роботи 5 задана у вигляді таблиці:

5	а	Ь	#
з	з, а, К	з, Ь, К	Я1, #,Ь
91	Я/, #,ь	Я/, #,Ь	Я/, #,Ь

2.2. Приклад. Побудувати машину Тюрінґа, яка застосовна до всіх слів в алфавіті X = {0,1} і замінює на 1 кожну другу букву вхідного слова.

Для розв'язання цієї задачі потрібно навчитися визначати чи зна­ходиться головка МТ під буквою, яка міститься на парній позиції вхі­дного слова. Для цього розглянемо два стани з і , в які керуючий пристрій буде переходити почергово при русі головки МТ праворуч і аналізі слова буква за буквою, починаючи з першої букви. Таким чином, якщо МТ перебуває в стані з, то вона аналізує букву, що знаходиться на непарній позиції у вхідному слові; якщо ж МТ пере­буває в стані д₁, то вона аналізує букву, що знаходиться на парній позиції. Домовимося також, що МТ не змінює порожнього слова. От­же, необхідно визначити роботу МТ так, щоб в стані з головка МТ не змінювала букви, а в стані д₁ замінювала 0 і 1 на 1. Підсумовуючи все вищесказане побудуємо граф МТ наступним чином:

Шукана МТ задається як п'ятірка МТ = (^,А, 5, з,/), де ^ = {з, 31, 4/}, А = {0,1, #}, X = У = {0,1}, О = {#}, і програма роботи 5 задана у вигляді таблиці:

5	0	1	#
з	41, 0, Д	41,1,Д	4/,
41	з, 1, Д	з, 1, Д	4/,

2.3. Приклад. Побудувати машину Тюрінґа, яка застосовна до всіх непорожніх слів в алфавіті X = {а, 6, с} і дописує вкінці вхідного слова його першу букву.

Для розв'язання даної задачі необхідно виконати наступні дії:

• запам'ятати першу букву;

• перемістити головку МТ праворуч під першу порожню ко­мірку і записати в неї першу букву.

0,1/1;Д

\ 0/0,1/1; Д

Як переміщуватися праворуч ми вже знаємо з попередніх при­кладів. Але як запам'ятати першу букву? Адже в МТ немає іншої пам'яті, крім стрічки, а запам'ятовувати букву в якій-небудь комірці немає сенсу: як тільки головка МТ переміститься ліворуч чи право­руч від цієї клітки, МТ відразу ж забуде дану букву. Як же вийти з цієї ситуації"? Стандартним вирішенням цієї проблеми є наступне - для кожної букви треба використовувати окрему множину станів. Якщо першою буквою є а, то потрібно перейти в стан д₁, в якому головка МТ переміщується праворуч і записує вкінці слова букву а. Якщо ж першою буквою є буква 6, то треба перейти в стан д₂, в яко­му виконуються ті ж самі дії, тільки вкінці слова дописується буква 6. В випадку, якщо першою була буква с, переходимо в стан , в якому дописуємо вкінці вхідного слова букву с. Цей прийом будемо використовувати і надалі для запам'ятовування різних букв вхідного слова. Підсумовуючи все сказане, граф МТ можна зобразити насту­пним чином:

а/а,Ь/Ь,с/с;К

Програма роботи 5 машини Тюрінґа МТ = А, 5, з, я/), де Я = {з,Яі ,Я2 ,Яз ,Я/}, А = {а,Ь,с, #}, X = У = {а,Ь,с}, Б = {#}, задається у вигляді таблиці:

5	а	Ь	с	#
з	д1 ,а,Я	Я2, Ь, Я	Яз, с, Я	—
Яі	д1 ,а,Я	я1 ,Ь,Я	Я1 ,с, Я	Я/, а, Ь
Я2	д2, а, Я	Я2, Ь, Я	Я2, с, Я	Я/ ,ь,т
Яз	Яз, а, Я	Яз ,Ь,Я	Яз, с, Я	Я/ ,с,ь

2.4. Приклад. Побудувати машину Тюрінґа в алфавіті А = {а, Ь}, яка працює наступним чином: якщо перша і остання буква непоро­жнього вхідного слова співпадають, то слово залишається незмінним, в протилежному випадку замінює його на порожнє слово.

Для розв'язання цієї задачі потрібно запам'ятати першу букву вхідного слова, перемістити головку МТ під останню букву і порів­няти її з першою. Якщо ці букви одинакові, то МТ має перейти в кінцевий стан і зупинити свою роботу, в протилежному випадку - стерти всі букви в слові. З попереднього прикладу ми вже знаємо, що для кожної букви потрібно створити свою множину станів для запа­м'ятовування даної букви і порівняння її з останньою буквою. Нехай такими станами для букви а будуть д₁, в якому МТ запамя'товує а і , в якому перевіряється чи останнью є буква а. Аналогічні стани для букви Ь позначимо через і . Якщо ж в стані головка МТ аналізує букву Ь або в стані головка МТ аналізує букву а, то ці букви витираються (замінюються порожнім символом і МТ пере­ходить в новий стан , в якому головка МТ переміщується ліворуч на початок слова, стираючи при цьому всі букви. Таким чином, граф МТ буде мати наступний вигляд.

а/а,Ь/Ь;Н

Отже, МТ задається як п'ятірка МТ = (^,А, 5, 5,/), де Я = І⁵, Яі, Я/}, А = {а, 6, #}, X = У = {а, 6}, Б = {#}, і програма роботи 5 задана у вигляді таблиці:

5	а	6	#
5	д1, а, К	Яз ,6, К	—
Яі	д1, а, К	Я1, 6,К	Я2,
Я2	Я/, а, Ь	Яб,	—
Яз	Яз, а, К	Яз ,6, К	Я4,
Я4	Яб,	я/ ,6,£	—
Яб	Яб,	яб ,	Я/, #,К

2.5. Приклад. Побудувати машину Тюрінґа, яка застосовна до всіх слів в алфавіті X = {а, 6} і видаляє із вхідного слова його другу букву.

На перший погляд, здається, що таку МТ побудувати надзвичай­но просто: достатньо змістити головку МТ на одну букву праворуч, а потім витерти другу букву вхідного слова. Але вкінці роботи МТ вихідне слово не повинно містити пропусків, тому після стирання другого символу потрібно стиснути слово, тобто перемістити першу букву в комірку праворуч. Проте, переміщуючись праворуч до другої букви, а потім повертаючись назад до першої букви, ми виконуємо зайву роботу: яка різниця чи переносити першу букву в порожню комірку чи в комірку з якоюсь буквою? Тому запам'ятовуємо першу букву, стираємо і записуємо її замість другої букви. Крім того, вва­жатимемо, що порожнє слово МТ не змінює. Отже, граф МТ, матиме наступний вигляд:

Проаналізуємо роботу МТ на вхідному слові, яке містить тільки одну букву. Аналізуючи дану букву головка МТ зітре її, перемісти­ться на одну комірку праворуч і запише в порожню комірку дану букву. Таким чином, слово із однієї букви просто зміститься на ко­мірку праворуч. Це допустимо, адже комірки стрічки ніяким чином не номеруються, тому розташування слова на стрічці ніяк не фіксу­ється і переміщення слова ліворуч чи праворуч неможливо поміти­ти. В зв'язку з цим не вимагається, щоб вихідне слово обов'язково знаходилось на тому ж місці, де було вхідне слово: результат може зміститися ліворуч чи праворуч від початкового місця.

Шукана МТ задається як п'ятірка МТ = (^,А, 5, 5,/), де ^ = І⁵, Зі,32,3/}, А = {а, 6, #}, X = У = {а, 6}, Б = {#}, і програма роботи 5 задана у вигляді таблиці:

5	а	6	#
5	зі, #,Д	32, #,Д	з/, #,Д
Зі	3/, а, Д	3/, а, Д	3/, а, Д
32	3/, 6, Д	3/, 6, Д	3/, 6, Д

2.6. Приклад. Побудувати машину Тюрінґа, яка за другою буквою непорожнього слова в алфавіті X = {0,1, 2} вставляє букву 2.

Шукана МТ має спочатку вивільнити місце для букви 2. Для цього потрібно якимось чином "розтиснути"слово. Ми можемо запа­м'ятати першу букву, стерти, записати її в комірці ліворуч, а потім в порожню комірку записати букву 2. Але, аналогічно як в попе­редньому прикладі, можна зробити це простіше: запам'ятати першу букву, записати на її місце букву 2, а потім переміститися ліворуч і записати в порожній комірці першу букву вхідного слова. Таким чином, отримуємо наступний граф МТ:

Отже, МТ задається як п'ятірка МТ = (Я, А, 5, з, д;), де Я = {з, д1 ,д₂, д₃, д;}, А = {0,1, 2, #}, X = У = {0,1, 2}, Б = {#}, і про­грама роботи 5 задана у вигляді таблиці:

5	0	1	2	#
з	41, 2,Ь	42, 2, Ь	4з, 2, Ь	—
	—	—	—	4;, 0,Е
42	—	—	—	4;, 1,Я
	—	—	—	4і, 2, Я

2.7. Приклад. Побудувати машину Тюрінґа в алфавіті А = {1, 2, 3}, яка у непорожньому вхідному слові замінює всі букви 3 на букви 2 і впорядковує послідовність букв 1 і 2 так, щоб спочатку були записані букви 1, а потім букви 2.

Шукана МТ має впорядкувати вхідне слово, замінивши при цьо­му всі букви 3 на букви 2. Принцип її роботи може бути описаний наступним чином. Як завжди, на початку роботи МТ знаходиться в початковому стані з і її головка аналізує першу букву вхідного слова. В стані д₁ головка МТ аналізує всі букви 1 слова, рухаючись праворуч, доти, поки не знайде першу букву 2 або 3. Далі, керую­чий пристрій переходить в стан , в якому головка МТ, рухаючись праворуч, аналізує букви 2 і 3, міняючи при цьому 3 на 2, до того часу, поки не побачить наступну 1. Після цього вона міняє місцями

в стані д_з 1 з 2, що знаходиться ліворуч і знову повертається в по­чатковий стан, повторюючи далі аналогічні кроки аж поки вхідне слово не буде впорядковане. Граф МТ має вигляд:

1/1;Д

^(д^) )2,з/2;Д

Проаналізуємо роботу даної МТ на вхідному слові 132113.

(5,132113) —

• (дз, 122213)

• (5,112213)

• (д2, 112213)

• (дз, 112223)

• (92, 111223)

(Я1, 132113) —

• (5,121213)

(я1, 112213)

• (9з, 112223)

• (5,111223)

• (92, 111223)

(92, 122113) — (92,121213) —

• (91, 112213) —

(5,112123) —

• (91, 111223) —

— (92, 111222#)

Елементи теорії алгоритмів, формальних мов та автоматів в прикладах і задачах 1

О 38

•О- 39

О 168

{|||| — 301

Наприклад, ||||||||| — ||||| — | і /(9) = 1. 301

(91, 111223) —

(9/, 111222)

—

Шукана МТ задається як п'ятірка МТ = (^,А, 5, 5,9/), де ^ = {5, 91,92, Яз, Я/}, А = {1, 2, 3, #}, X = {1, 2,3}, У = {1, 2}, В = {#}, і програма роботи 5 задана у вигляді таблиці:

5	1	2	3	#
5	91, 1,Д	92, 2,Д	92, 2,Д	—
Я1	91, 1,Д	92, 2,Д	92, 2,Д	Я/,
Я2	Яз, 2,Т	92, 2,Д	92, 2,Д	Я/,
Яз		5,1,£	—	—

2.8. Приклад. Побудувати машину Тюрінґа в алфавіті А = {а, 6}, яка подвоює у вхідному слові всі входження букви 6.

В попередніх прикладах ми бачили, що вставляти чи витирати навіть одну букву зі слова досить непросто. Тому нове слово будемо будувати на вільному місці, а саме, праворуч від вхідного, попере­дньо поставивши вкінці вхідного слова допоміжний символ " = ". Для

цього в початковому стані з переміщуємося праворуч вкінець слова, міняємо перший порожній символ на " = "і переходимо в новий стан

41.

Далі, нам потрібно переносити букви за знак " = ", при цьому подвоюючи кожного разу букву Ь. Для цього в стані д₁ "біжимо"на початок слова, переходимо в стан д₂ і запам'ятовуємо першу букву: якщо це буква а, то переходимо в стан д_з, якщо Ь - в д₄. В станах д_з і д₄ "біжимо"праворуч до першої порожньої комірки і записуємо в неї першу букву, при цьому дублюємо її в стані , якщо цією буквою є Ь. Потім знову повертаємося ліворуч до тієї букви, яка стала першою у вхідному слові, і повторюємо описані вище дії з цією новою першою буквою.

Даний цикл завершується тоді, коли при русі праворуч ми в стані

д₂ побачимо в якості першої букви символ " = ". Насамкінець, вити­" м м • . „

а/а,Ь/Ь;Н

раємо допоміжний символ " = "і переходимо в кінцевий стан /. Враховуючи все вище сказане, будуємо граф МТ.

а/а,Ь/Ь,=/=;Н

#/=;і

^(ді^ ^(02)

а/а,Ь/Ь,=/=;Н

Програма роботи 5 машини Тюрінґа МТ = А, 5, з,д/), де Я = {з,Я1 ,Я2,Яз,Я4,Я5,Я/}, А = {а,Ь, =, #}, X = У = {а, Ь}, Б = {#, =}, задається у вигляді таблиці:

5	а	Ь	=	#
5	8, а, К	8, Ь, К	—	Яі, =,£
Яі	,а,Ь	Яі ,Ь,Ь	яі, =,£	Я2, #,К
Я2	Яз, #,К	Я4, #,К	Яї, #,К	—
Яз	Яз, а, К	Яз, Ь, К	Яз, =,К	я1 ,а,£
Я.4	^4, а, К	я4 ,Ь,К	я4, =, К	Я5 ,Ь,К
Я5	—	—	—	Яі ,Ь,Ь

2.9. Приклад. Побудувати машину Тюрінґа в алфавіті А = {а, Ь},

• " ' І! І!

яка подвоює слово, поклавши між ним і його копією знак " = ".

Ця задача розв'язується аналогічно до попередньої: праворуч від вхідного слова дописуємо символ " =", потім повертаємося на початок слова і в циклі копіюємо всі його букви в порожні комірки праворуч.

Однак, тут є одна відмінність: букви вхідного слова не видаля­ються, і це приводить до такої проблеми. Записавши справа копію наступного слова, ми повинні повернутися до вхідного слова в пози­цію цієї букви і потім перемістится праворуч до наступної букви. Але як дізнатися, в яку позицію вхідного слова потрібно повернутися? В попередній задачі ми завжди поверталися до першої з букв вхідного слова, які залишилися, а тепер ми не витираємо букви і тому не­зрозуміло, які букви ми вже продублювали, а які ще ні. Нагадаємо, що в МТ комірки стрічки ніяким чином не номеруються, немає в МТ і лічильників, які б дозволили визначити, скільки букв ми вже продублювали.

В загальному випадку, проблема, з якою ми стикнулись, насту­пна: як зафіксувати на стрічці деяку позицію, в якій ми вже були і до якої пізніше повинні повернутися? Зазвичай ця проблема вирішу­ється таким чином. Коли ми опиняємося в цій позиції перший раз, то замінюємо активну букву на її двійник - на новий допоміжний символ, причому різні символи замінюємо різними двійниками. Пі­сля цього ми виконуємо якісь дії в інших місцях стрічки. Щоб потім повернутися до нашої позиції, потрібно просто відшукати на стрічці ту комірку, де знаходиьться буква-двійник. Потім в активній комірці можна відновити попередню букву.

Таким чином, побудуємо МТ за наступним планом:

• спершу записуємо символ " = "після останньої букви слова;

• потім повертаємося під першу букву вхідного слова;

• далі, замінюємо активну букву на її двійник (а на А, Ь на В), переміщуємося праворуч до першої вільної комірки і запису­ємо в неї букву, яку запам'ятали;

• після цього повертаємося ліворуч до комірки з двійником, відновлюємо попередній символ і переміщуємося праворуч до наступної букви;

• анлогічним чином в циклі дублюємо решту букв вхідного слова;

• наостанок, коли ми продублюємо останню букву вхідного слова і повернемося до її двійника, то далі, після руху пра­воруч на одну позицію, ми побачимо символ "=". Це ознака того, що вхідне слово повністю продубльоване і тому роботу МТ потрібно зупинити.

а/а,Ь/Ь,=/=;Д

Таким чином, шукана МТ задається як п'ятірка А, 6, 5, з/), де Я = {5, Зі,32, Зз, 34, 3/}, А = {а, Ь, А, В, =, #}, X = {а, Ь}, У = {а, Ь, = }, Р = {А, В, #}, і програма роботи 6 задана у вигляді таблиці:

6	а	Ь	А	В	=		#
5	5, а, К	5, Ь, К	—	—	—		Зі, =,£
Зі	31, а, Ь	Зі ,Ь,Т	32, а, К	32, Ь, К	Зі,		32, #,К
32	Зз, А, К	34 ,В,К	—	—	У,	=, К	—
Зз	Зз, а, К	Зз, а, К	—	—	Зз,	=, К	Зі, а, Ь
34	34, а, К	34, Ь, К	—	—	34,	=, К	Зі ,Ь,Т

Вправи до лекції 2.

В задачах 2.1-2.16 побудувати машину Тюрінґа, яка застосовна до всіх слів в алфавіті А, і виконує наступну роботу.

1. А - український алфавіт. Дописує зліва до вхідного слова ш слово ВУЗ (ш ^ ВУЗш).

2. А = {Н, П, У}. Дописує справа до вхідного слова ш слово ПНУ (ш ^ шПНУ).

3. А = {а, Ь}. Залишає в слові тільки першу букву (порожнє слово не міняє).

4. А = {а, Ь}. Залишає в слові тільки останню букву (порожнє слово не міняє).

5. А = {а, Ь, с}. Якщо вхідне слово не містить букви с, то замінює всі букви а на Ь. В іншому випадку видає слово з однієї букви с.

6. А = {0,1, 2, а}. З'ясувати чи є вхідне слово записом числа в трійковій системі числення. Відповідь: 1 - якщо є, 0 - в протилежно­му випадку.

7. А = {0,1, 2}. Вважаючи вхідне слово записом числа в трійковій системі числення, видалити з нього всі незначущі нулі.

8. А = {0,1, 2}. Вважаючи вхідне слово записом числа в трійковій системі числення, з'ясувати чи ділиться воно на 3. Відповідь: 1 - якщо ділиться, 0 - в протилежному випадку.

9. А = {а, Ь}. В непорожньому вхідному слові поміняти місцями першу та останню букви.

10. А = {|}. Якщо вхідне слово має непарну довжину, то замінити його на слово |, в іншому випадку - на порожнє слово.

11. А = {а,Ь,с}. Якщо вхідне слово має парну довжину, то зали­шити в ньому тільки праву половину.

12. А = {0,1}. Визначити чи вхідне слово є симетричним (полін- дромом), тобто ш = ш^Е. Відповідь: 1 - так, є, 0 - ні, не є.

13. А = {а, Ь}. Замінити у вхідному слові кожне входження букви Ь на аЬ.

14. А = {а,Ь}. Видалити із вхідного слова кожне входження під­слова Ьа.

15. А = {а, Ь}. Подвоїти кожну букву вхідного слова (наприклад, аЬа ^ ааЬЬаа).

16. А = {а,Ь}. Обернути вхідне слово (наприклад, ааЬ ^ Ьаа). Лекція 3. Функції, що обчислюються МТ

В даному параграфі ми розглядатимемо функції, для яких існує машина Тюрінґа, що їх обчислює. Дані функції визначаються по­ведінкою МТ. Аргументи (вхідні слова) з'являються на стрічці до початку обчислення, а значення функції для цього аргументу - сло­во, яке залишається на стрічці, коли обчислення завершено. Відмі­тимо, що при аналізі деяких вхідних слів МТ ніколи не переходить в кінцевий стан, і, отже функція може бути не визначена для деяких вхідних слів (аргументів). В загальному випадку, кажемо, що фун­кція / : (X * )^п ^ У * є частково визначеною функцією, якщо вона не визначена для деяких наборів аргументів (х₁,... ,х_п) Є (X*)^п, тоб­то коли область визначення / є підмножиною (X * )^п. Якщо областю визначення / співпадає з (X*)^п, то кажемо, що функція / повні­стю визначена на (X*)^п. Якщо функція / не визначена на наборі (х₁,... ,х_п), то писатимемо /(х₁,... ,х_п) =|.

Кажемо, що частково визначена функція / : (X * )^п ^ У * обчи­слюється з допомогою машини Тюрінґа

МТ = (Я, А = X Ці У Ці Б, 5, з, д;),

якщо для кожного набору (х₁,..., х_п) Є (X*)^п, на якому / визначена

(з,х₁ * х2 * ... * хп) ^ (;,у),

де у = / (х₁,..., х_п) Є У *, а * Є Б - спеціальний допоміжний символ, який розділяє вхідні аргументи; і для кожного набору (х₁,..., х_п) Є (X*)^п, для якого функція не визначена МТ ніколи не перейде в кін­цевий стан д;.

Надалі, найчастіше розглядатимемо числові функції / : (N0)^п ^ N0, де N0 = N Ц{0}.

3.1. Приклад. Покажемо, що функція / : N0 — N0, /(п) = 0 обчи­слюється з допомогою деякої машини Тюрінґа.

Вважатимемо, що невід'ємні цілі числа записані в двійковій си­стемі числення. Для побудови МТ, яка правильно обчислює дану функцію, достатньо визначити стан, в якому МТ замінює всі цифри вхідного слова на порожній символ, друкує цифру 0 і зупиняє роботу. Граф шуканої МТ має вигляд:

0,1/#;Д

3.2. Приклад. Побудуємо машину Тюрінґа, яка обислює функцію / : N — N /(п) = п + 1 (вважаємо, що натуральні числа задані в трійковій системі числення).

Нехай 5 - стан, в якому головка МТ рухається в кінець слова. Дійшовши до першої порожньої клітинки, головка МТ переходить ліворуч під останню цифру слова і керуючий пристрій переходить в стан д.

д - це стан, в якому МТ додає одиницю до тієї цифри, яку во­на аналізує в даний момент часу. Спочатку це остання цифра чи­сла; якщо це цифра 0 або 1, то керуючий пристрій замінює її на 1 або 2 відповідно і МТ зупиняє роботу. Але, якщо дана цифра є 2, то керуючий пристрій замінює її на 0 і головка переміщується ліво­руч, залишаючись в стані д. Таким чином, тепер МТ додоватиме 1 до попередньої цифри. Якщо ця цифра дорівнює 2, то МТ міняє її на 0 і переміщується ліворуч, залишаючись як і до того в стані д, тобто керуючий пристрій повинен виконати ту ж саму дію - збіль­шити активну цифру на 1. Якщо ж головка перемістилася ліворуч, а в активній комірці немає цифри (а є #), то МТ записує туди 1 і преходить в кінцевий стан /.

Відмітимо, що для порожнього вхідного слова наша задача не визначена, тому на цьому слові МТ може поводитися як завгодно. В нашій програмі, наприклад, на порожньому вхідному слові МТ зупиняється і видає 1.

Граф МТ матиме вигляд:

2/0;Ь

0/0,1/1,2/2;Д

#/#;Ь

-Н Я

-И 5

#/1,0/1,1/2; Д

МІЯЇ

Під унарною системою числення розумітимемо запис невід'єм­ного цілого числа з допомогою "паличок" — мусить бути виписано стільки паличок, якою є величина числа, наприклад, 2 ^ ||, 5 ^ |||||, 0 ^ <пороржній символ>.

3.3. Приклад. Побудуємо машину Тюрінґа, яка обислює функцію / : М₀ х М₀ ^ М₀, /(п,т) = п + т (вважаємо, що натуральні числа задані в унарній системі числення).

МТ починає аналізувати вхідне слово в конфігурації

(5, || ... | * || ... |), або в конфігурації (5, * || ... |), якщо п = 0.

Шукана машина Тюрінґа, яка правильно обчислює дану фун­кцію двох змінних, може працювати, наприклад, таким чином. Якщо п = 0, то вона стирає * і зупиняє роботу. В іншому випадку, видаляє першу паличку |, переміщується праворуч до * і на її місці записує |. Таким чином МТ = (ф, А = X У У У Б,5,5,д?), де ^ = {5,д,д?}, X = У = {|}, Б = {*}, а програма роботи 5 задана у вигляді таблиці:

5	|	*	#
5	я, #,Д	я?, #,Д	—
я	Я,	Я!,	—

3.4. Приклад. Побудуємо машину Тюрінґа, яка обчислює частково визначену функцію / : М₀ ^ М₀, /(х) = х — 2.

Ідея розв'язання задачі така ж як і в прикладі 3.2. Нехай 5 - стан, в якому головка МТ рухається в кінець слова. Дійшовши до першої порожньої клітинки, головка МТ переходить ліворуч під останню ци­фру слова і керуючий пристрій переходить в стан д₁. Якщо в стані д₁, МТ аналізує цифри 2, 3,..., 9, то вони замінюються на 0,1,..., 7 від­повідно і МТ зупиняє роботу. В іншому випадку, - якщо це цифри 0 або 1, то керуючий пристрій замінює їх на 8 або 9 відповідно і голов­ка переміщується ліворуч, керуючий пристрій при цьому переходить

в стан д₂, в якому МТ віднімає 1 від попередньої цифри. Якщо ця цифра дорівнює 1, 2,..., 9, то МТ міняє її на 0,1,..., 8 і зупиняє ро­боту. Інакше, замінює 0 на 9 і переміщується ліворуч, залишаючись як і до того в стані д₂, тобто керуючий пристрій повинен виконати ту ж саму дію - зменшити активну цифру на 1 і т.д. Якщо ж головка, перемістившись ліворуч, в стані д₂ аналізує # (це має місце тільки для чисел 0 та 1), то подальші дії МТ не визначені і до таких чисел МТ не застосовна. Побудуємо граф даної МТ.

3.5. Приклад. Побудуємо машину Тюрінґа, яка обислює функцію / : N0 х N0 ^ N0, /(п,т) = |п — т| (вважаємо, що натуральні числа задані в унарній системі числення).

Нехай початковою конфігурацією є (8, | ... | * | ... |). Ідея розв'я-

^т

зання задачі така. МТ переміщується під першу паличку другого числа, і порівнює числа наступним чином. В станах д_і та д₂ МТ відмічає почергово по одній палочці (замінюючи | на *) в обох по­слідовностях | і вичерпавши одну із послідовностей робить висновок, яка з них складається з більшої кількості паличок. Далі, в станах д₃ або д₄ витирає всі * і на стрічці залишається п — т паличок, якщо п > т, або т — п, - якщо п < т. Граф МТ має вигляд.

Проілюструємо роботу МТ на прикладі. Нехай на вході маємо слово | * |||. Тоді:

(з, | * |||) — (з, |*|||) — (#1, || * |||) — (Я2, |* * ||) — (Я2, | * *||) — (я₁, ***|||) ^ (я₁, ***||) — (я₂, ****|) ^ (д₂, #****|) — (д₃, ****|) ^ (Яз, |#) - (Яу, ||). " "

3.6. Приклад. Побудуємо МТ, яка обчислює функцію / : N0 х N — N /(п,т) = НСД(п,т).

Нехай цілі невід'ємні числа п та т задані в унарній системі числе­ння. Знайдемо їх найбільший спільний натуральний дільник, кори­стуючись алгоритмом Евкліда. Даний алгоритм базується на таких рекурентних формулах для знаходження НСД:

!НСД(п — т, т), п > т; НСД(п, т — п), п < т; п, п = т.

Побудуємо МТ для відшукання НСД, процес обчислення на якій базуватиметься на почерговому використанні циклів порівняння і віднімання.

|/И */*;ь */#,І/И

Процес побудови МТ будемо супроводжувати ілюстрацією кон­фігурацій для обчислення НСД(4, 6). Початкова конфігурація ма­тиме вигляд (з, |||| * ||||||). Спершу в станах з та д₁ перенесемо пер­шу паличку на місце *. В результаті цього отримаємо конфігурацію (з, ||||||||||). Далі, використовуючи допоміжні мітки а та Ь в станах д₂

та д_з будемо порівнювати числа п і т. При цьому МТ працювати­ме так, як би працювала людина, яка порівнює дві довгі послідов­ності з |, які відразу важко повністю переглянути. А саме, людина відмічає якимось чином почергово по одній палочці в обох послідов­ностях і вичерпавши одну із послідовностей робить висновок, яка з них складається з більшої кількості паличок. Машина ж замінює першу паличку другого числа на Ь, потім замінює першу паличку першого числа буквою а, потім знову повертається до паличок дру­гого числа і т.д. Після декількох тактів на стрічці виникає конфігу­рація (д_з, #ааааЬЬЬЬЬ|), в якій перше число вже вичерпане, а друге ще ні. Далі, МТ переходить в стан д₄, в якому її головка перемі­щується праворуч, витираючи мітки а та замінюючи мітки Ь на | . Після цього вона переходить в стан д₂ для порівняння чисел п = 4 і

т—п = 2, знаходячись при цьому в конфігурації (д₂, ||||||) під першою паличкою числа т — п = 2. Таким чином, після циклу порівняння

виконано цикл віднімання від другого числа першого, в результаті

якого менше число п витерто, а більше число т розбито на п і т — п.

Далі, знову проходить цикл порівняння, який на цей раз за­кінчується вичерпанням другого числа (що знаходиться праворуч), яке в цьому випадку є меншим. При цьому одержимо конфігура­цію (д₂, ||ааЬЬ#). Наступний такт породжує конфігурацію (д₅, ||ааЬЬ) і починається цикл віднімання від першого числа другого, тобто сти­рання всіх букв Ь і заміна букв а палочками. Після цього, МТ знову

переходить в стан д₂ в конфігурації (д₂, ||||). Цей процес триває доти, доки задачу не буде зведено до випадку двох рівних між собою чисел

(в нашому випадку ми вже досягли цього). Наостанок, починається останній цикл порівняння, в якому одне з чисел витирається, МТ пе­реходить в кінцевий стан у і на стрічці залишається число, записане в унарній системі числення, яке, згідно алгоритму Евкліда, дорівнює НСД(п,т).

Граф шуканої МТ має вигляд:

|/|;Д а/а,Ь/Ь;Д а/а,Ь/Ь;Ь

#/#;Д

а/І,Ь/#;Ь

а/#,Ь/|; Д

Відмітимо, що якщо перше число п = 0, то перебуваючи в кон­фігурації (5, ... |) МТ переходить в кінцевий стан і на виході дає число т = НСД(0, т), т Є N.