2.3 Контрольні питання

1 Алгоритмічна система нормальні алгоритми Маркова (НАМ).

2 Поняття функції обчислюваної за Марковим.

3 Побудова НАМ для нуль – функції, ф-ції безпосереднього слідування, селекторної ф-ції.

4 Поняття еквівалентних відносно алфавіту А нормальних алгоритмів Маркова

5 Композиція НАМ. Приклад.

6 Розгалуження двох НАМ під керуванням третього. Приклад.

7 З’єднання НА. Приклад.

8 Повторення одного НА під керування іншого. Приклад.

9 Принцип нормалізації.

3 Машина Тьюрінга

3.1 Теоретичні поняття і визначення

Алгоритмічну систему, в якій правила, що визначають дію алгоритму, побудовані за командно-адресним принципом для деякої машини з необмеженою пам’яттю, називають машиною Тьюрінга (МТ).

Розглянемо найпростіший приклад.

Нехай є нескінченна з 2-х боків паперова стрічка, на якій можна писати букви в клітинках. Є головка, яка: може знаходитись в одному із 2-х різних станів,читає і записує букви в клітинки стрічки; може рухатися вліво й вправо(п) вздовж стрічки та стояти(с).

Складемо таблицю, яка описує машину Тьюрінга для обчислення функції S(х) = x + 1 в алфавіті A={I}.  - спеціальний пустий символ.

Символ {!} означає зупинку МТ.

	q0	q1
	Iq1c
I	Iq0п	!

	I	I	
	q0

	I	I	
		q0
	I	I	
			q0

	I	I	I	
			q1

х = II	початкове число
	Iq0  Iq0п
	IIq0  Iq0п
	q0  Iq1с
	Iq1  I
S = III	результат

Висновок

Яке б число не було записане на стрічці МТ, головка буде рухатися вправо до пустої клітинки, запише в пусту клітинку I і зупиниться. На стрічці буде записано число х + 1, замість х. Тобто буде обчислена функція S(x) = x +1.

Тепер перейдемо до формального визначення Машини Тьюрінга (МТ).

МТ запропонована англійським математиком А. Тьюрінгом в 1937 р. Це алгоритмічна система, яка визначає загальний способів задання алгоритмів.

1. У цій системі виконується запис інформації на нескінченній в обидва боки стрічці, розбитій на клітини. У клітинку можна записати тільки одну букву скінченого алфавіту А = {a₁, …a_n}.

2. Цю букву можна оглядати (читати, записувати) спеціальним чутливим елементом – так званою головкою МТ.

Головка МТ може знаходитись в одному із скінченої кількості різних станів:

Q = {q₀, q₁,…q_m}

Головка може записувати в клітинці, яку оглядає, будь-яку букву з алфавіту А і залишатись на місці або переміщуватись праворуч чи ліворуч уздовж інформаційної стрічки на одну клітинку.

Задати МТ означає задати таку п’ятірку об’єктів:

А, Q, q₀, , Р, де

А – алфавіт машини (зовнішній алфавіт);

Q – скінчена непуста множина станів машини, (А  Q = );

q₀ - початковий стан МТ;

 - спеціальний пустий символ (  A  Q);

Р - програма роботи МТ;

МТ виконує команди.

Команда має вигляд aq  bqd (aqbqd)

a, b,  A

q, q Q

d = {S, L, R}.

Програма МТ – це скінчена множина команд, причому не існує таких 2-х команд, які б мали однакові перші 2 символи. Як виконується команда aq  bqd ? Головка МТ: - знаходиться в стані q; - читає записану в клітинці букву а; - записує в цю клітинку нову букву b ( яка може збігатися з буквою а); - переходить у стан q(який може збігатися зі станом q) і переміщується вздовж стрічки на величину d. Якщо d = S, то головка залишається на місці; ……. d = R, то відбувається зсув головки вправо на 1 клітинку; ……. d = L, то відбувається зсув головки вліво на 1 клітинку.

МТ зупиняється тоді і тільки тоді, коли жодна з команд програми не може застосовуватись або вказується символ {!}, що означає зупинку МТ.

Результатом роботи МТ після її зупинки є слово, записане на стрічці. Це слово називається заключним.

В цьому випадку МТ вважається застосовною до початкового слова.

Якщо МТ обробляє початкове слово нескінченно довго, то МТ.

вважається не застосовною до початкового слова.

Функціонування МТ можна описати за допомогою протоколу роботи над заданим початковим словом.

Нехай:

1. a₁, …a_ka_k+1,…a_k - слово, що виникає на стрічці в процесі роботи МТ.

2. МТ знаходиться в стані q.

3. Головка стоїть проти k-го символа слова.

Слово a1 …akqak+1…am (a1 …akak+1…am ) називається q конфігурацією.

Послідовність коніфгурацій при роботі МТ називається протоколом МТ.

Розглянемо приклад.

Створити МТ, яка всяке натуральне число n, написане в двійковій системі перетворює на число n + 1 теж записане в 2-ковій системі. Тобто реалізує S(x) = x + 1 обчислення ф-ції безпосереднього слідування.

Програму можна записувати: - у вигляді послідовності команд; - у вигляді спеціальної таблиці.

	Стан МТ
Символ	q0	q1	q2
	q1L	1q2L
0	0q0R	1q2L
1	1q0R	0q1L	!

Протокол МТ

1)  1 0  початкова конфігурація

q0

2)  1 0 

q0

3)  1 0 

q0

4)  1 0 

q1

5)  1 0   заключна конфігурація

q2

Початкове слово w = 10

Результат w₁ = 11.

З кожною МТ пов’язана часткова функція (словесна ф-ція) fмт : S(A)  S(A), де S(A) – множина слів в алфавіті А. Якщо МТ зупиняеться при роботі над початковим словом w, то значення ф-ції визначене і fмт (w) = w, де w - заключне слово на стрічці МТ. Якщо МТ не зупиняється, значення ф-ції не визначене на слові w.

Нехай задана часткова ф-ція f на множині S(A). Ця ф-ція називається обчислюваною за Тьюрінгом, якщо існує МТ така, що : Зовнішній алфавіт МТ співпадає з А. f(w)  fмт(w), (w)  S(A)

Приклад 1

Наведемо приклад МТ, яка незастосовна до будь-якого не пустого слова в алфавіті А = {I}



I



	Стан МТ			1)  I 
Символ	q0			q0
	Iq0L			2)  I 
I	Iq0L			q0
				3)  I I 
				q0
				4)  I I I 
				q0 Протокол МТ нескінченний.

Дія цієї МТ полягає в тому, що, почавши роботу з будь-якого непустого слова w, до цього слова приписується зліва символ I. Машина не зупиняється. Результат роботи не визначений, оскільки машина не застосовна до будь-якого непустого слова w  S(A).

Приклад 2

МТ, яка реалізує алгоритм додавання 2-х натуральних чисел в алфавіті А = {I}, B = {I, +}

Ідея алгоритму



І

+

І



1. Кожну I 1-го доданку стерти й записати її в кінці 2-го доданку.

2. Стерти знак +.

	Стан МТ
Символ	q0	q1	q2	q3
	q0 R	Iq2 S	q0 S	!
I	q1 R	Iq1 R	Iq2 L
+	q3S	+q1 R	+q2 L

P = I + I

1)  I + I 		2)   + I 		3)  + I 
q0		q1		q1
4)  + I 		5)  + I I 		6)  + I I 
q1		q2		q2
7)  + I I 		8)  + I I 		9)  + I I 
q2		q2		q0
10)  + I I 		11)  I I 		12)  I I 
q0		q3		q3
		fMT(I+I) = II		P1 = I I

Cуперпозиція машин Тьюрінга

З математичної точки зору МТ – це просто визначений алгоритм для переробки слів.

Кожна МТ забезпечує знаходження значення деякої словникової функції в алфавіті А

f_MT: S(A), де S(A) – множина слів А.

Тому природно ввести операцію суперпозиції МТ. Ця операція суперпозиції МТ буде еквівалентна суперпозиції функцій, що

представляють ці МТ.

Нехай МТ М1 обчислює ф-цію f1(w) в алфавіті А. А = {a1, …, an}

М2 обчислює ф-цію f2(w) в алфавіті А.

Значення суперпозиції f2(f1(w)) визначене тоді і тільки тоді, коли визначена ф-ція f1(w) і визначено значення ф-ції f2 на слові f1(w).

Побудуємо МТ М, яка буде суперпозицією машин М1 і М2 і обчислює суперпозицію f2(f1(p)).

Програма для обчислення суперпозиції f2(f1(p)) являється об’єднанням програм для обчислення ф-цій f1 і f2.

Початковий стан МТ М2 повинен збігатися із заключним станом МТ М1. Усі стани М2, крім початкового, повинні відрізнятися від станів М1.

Після перетворення програми М2, програми М1 та М2 об'єднуються в одну таблицю-програму МТ М.

Початковим станом М стає початковий стан М1 Заключним станом М стає заключний стан М2 Суперпозицію М машин М1 і М2 будемо позначати М2  М1. Як змінити стан МТ М2 ? Треба всі номери станів крім початкового збільшити на число, що збігається з номером заключного стану М1

Можливість будувати МТ за допомогою суперпозиції, розгалуження, циклів приводять до думки, що мова Тьюрінговського програмування дозволяє реалізувати будь-який алгоритм (в інтуітивному розумінні).

Теза Тьюрінга

Класи обчислюваних і обчислюваних за Тьюрінгом функцій збігаються.

Довести тезу Тьюрінга, як і тезу Черча, неможливо, оскільки саме поняття алгоритму (в інтуітивному розумінні) є неточним. Це не теорема і не постулат математичної теорії. Це твердження, яке пов'язує теорію з тими об'єктами, для опису яких її створено.

Підтвердженням тези Тьюрінга є,

• по перше математична практика;

• по друге, той факт, що опис алгоритму у термінах будь-якої іншої відомої алгоритмічної моделі може бути зведений до його опису у вигляді МТ.

2. Лабораторна робота №3

Тема. Машина Тьюрінга (МТ) та їх властивості.

Мета. Засвоїти основні поняття алгоритмічної системи Машина Тьюрінга.

Завдання.

1 Застосувати МТ, яка реалізує функцію S(x) = x +1 в алфавіті A = {|,0,1} для обчислення S(n), (де n порядковий номер студента в журналі), попередньо перевівши цей порядковий номер у 2-кову систему числення.

2 Створити МТ для обчислення функції I_mⁿ(х₁, х₂, ..х_m,.. х_n) =х_m ,

якщо х₁, х₂, ..х_m,.. х_n – числа записані в алфавіті A = {|}, а між числами х₁, х₂, ..х_m, ..х_n ставиться *, де m визначається так:

10, якщо n =1;

m= n якщо 1 n  10;

остача від ділення n на 10, збільшена на одиницю.

3 Створити машину Тьюрінга , яка переводить будь-яке натуральне число, записане в алфавіті A = {|}, в запис цього числа в m – значній системі числення.

4 Створити МТ, яка перетворювала б будь-яке натуральне число k,

записане в алфавіті A = {|} в число k+m, де m –визначене в пункті 2.

Приклад виконання завдання

Варіант 37. Виконав студент групи ЗІТ-***. Дата ***.

1 Застосуємо МТ, яка реалізує функцію S(x) = x +1 в алфавіті

A = {|,0,1} для обчислення S(n), (де n порядковий номер студента в журналі), попередньо перевівши цей порядковий номер у 2-кову систему числення. Нехай n=2₁₀ =10₂ .Тоді S(10₂ )=11_2. Нижче наведем програму МТ та протокол роботи МТ. Символ {!}

означає зупинку МТ.

	Стан МТ
Символ	q0	q1	q2
	q1L	1q2L
0	0q0R	1q2L
1	1q0R	0q1L	!

Протокол МТ

1)  1 0 

q0

2)  1 0 

q0

3)  1 0 

q0

4)  1 0 

q1

5)  1 1 

q2

2 Створимо МТ для обчислення функції I₄⁵(х₁, х₂, х_3, х₄, х₅) = х₄ , якщо х₁, х₂, х_3, х₄, х₅ – числа записані в алфавіті A = {|}, а між числами х₁, х₂, х_3, х₄, х₅ ставиться *.

	Стан МТ
Символ	q0	q1	q2	q3	q4	q5
|	|q1L	q1R	q2 R	q2 R	|q4R	q5R
*		q2R	q3 R		q5R
	q1R					!

3 Створимо машину Тьюрінга , яка переводить будь-яке натуральне число, записане в алфавіті A = {|} в запис цього числа в 4 – значній системі числення. Головка МТ нехай стоїть спочатку проти правого крайнього символу {|} в стані q₀.

	Q (Стан МТ)
A Символ	q0	q1	q2
|	q1 L	|q1L	|q2R
	!	1q2 S	q0L
0	!	1q2 S	0q2R
1	!	2q2 S	1q2R
2	!	3q2 S	2q2R
3	!	0q1 L	3q2R

4 Створимо МТ, яка перетворювала б будь-яке натуральне число k, записане в алфавіті A = {|} в число k+3. Головка МТ нехай стоїть спочатку проти лівого крайнього символу {|} в стані q₀.

	Стан МТ
Символ	q0	q1	q2	q3
|	|q0R
	|q1R	|q2R	|q3R	!

2. Контрольні питання

1 Алгоритмічна система Машина Тьюрінга (МТ).

2 Поняття функції обчислюваної за Тьюрінгом.

3 Суперпозиція МТ.

4 Розгалуження МТ.

5 Теза Тьюрінга .

6 Еквівалентність теорій (МТ, нормальних алгоритмів Маркова та ЧРФ).

7 Поняття про алгоритмічно розв′язувані проблеми та алгорит-мічно нерозв′язувані проблеми.

8 Проблема зупинки МТ.

9 Проблема розпізнавання самозастосовності МТ.

10 Проблема еквівалентності слів для асоціативних числень.