Проверить работу машины Тьюринга над некоторыми словами.

 

№
1.
2.	, если , если
3.	, если в данном слове количество букв a нечетно, bb, если четно
4.	, сели n нечетно, , если n – четно.
5.
6.
7.	, если слово начинается на ba, в других случаях
8.	, если , bb, если
9.	ab, если n – четно, xn, если n - нечетно
10.	an, если xn-1=a, x1x2…xn-2ab, если xn-1=b
11.	x1x3x2x4x5…xn
12.	ax1x2…xn-2b
13.	a, если n<4, x1…xn, если n>3
14.	a a, если в данном слове число букв нечетно, x1x2…xn-1, если четно
15.	, если x2=a, x1…xn, если x2=b
16.	bab, если слово начинается на ab, x1x2 в других случаях
17.	x1x2...xnb, если n – четно, bx1x2…xn, если n – нечетно
18.	a b, если x2=a, x1…xn-1, если x2=b
19.	, если n – нечетно, x1x2…xn-1xnxn, если n - четно
20.	an, если x1=a, x2, если x1=b
21.	x1x2…xn-1
22.
23.	x1xnx2x3…xn-1
24.	bnx1…xn
25.	(ab)n
26.	x1x2…xn-2xn-1xn
27.	x1, если n – нечетно, xn, если n - четно
28.	xnxn-1…x1
29.
30.	ab, если слово начинается на ba, x1…xn-1 в других случаях

 

Задание 2.

1. Построить машину Тьюринга, вычисляющую числовую функцию .

Проверить работу построенной машины над некоторыми наборами значений переменных.

 

№
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

Задание 3.

1. Написать формулу числовой функции , вычислимой машиной Тьюринга с множеством внутренних состояний , где 0 – заключительное, а 1 – начальное состояния, если машина задана своей программой.

Проверить работу машины Тьюринга с некоторым набором значений аргументов.

№	n
			1П2	1П3	П4	Л5	Л5	Н0
	П1	1П2	1П3	П4	Л6	Л0

			---	1П5	П4	Н0	---	Н0
	1П2	П3	П3	П4	1П6	П6

			П2	П3	Л4	1Н0	1Л6	1Л4
	П1	П2	1П3	П5	1П5	1Л6

			1П4	Л3	Н0	1Л5	1П6	1Н0
	1П2	1П1	Л3	1П4	1Л5	1П6

			---	1П3	П4	Л5	Л5	1Н0
	П2	П2	1П3	1Л6	1Л6	1Л6

			П2	1П3	П4	Л5	Л5	---
	П1	1П2	1П3	П4	Л6	Н0

			П4	1П3	1П1	Л5	Л5	Н0
	Л2	1Л2	1П3	П4	Л6	1Л6

			1П2	1П3	1П4	Л5	Л6	Л6
	1П1	П2	1П3	---	Л5	1Н0

			1П2	1П3	Л4	Л4	1Л6	1Л0
	П1	1П2	П3	Л5	1Л5	---

			П2	П3	П4	Л5	Л5	1Н0
	П1	П2	1П3	П4	Л6	1Л6

			П2	1Н0	1П5	1Н0	1Л6	1Н0
	П1	1П3	1П4	1П4	1Л5	1Л6

			П2	1П3	1Л4	1П5	1Л6	1Н0
	П1	П2	1П3	1Л4	1П5	1Л6

			1П4	1П3	1П1	1П5	1П6	Н0
	Л2	1Л2	1П3	1П4	---	1Н0

			Н0	П3	1П4	1П5	---	1Л1
	Н2	П2	П3	1П4	1Л6	1Л6

			1П2	Л3	1П6	1Л5	1Л3	1Н0
	1П1	1П2	П4	1П4	1Л5	1П6

			1П2	П3	П4	Л5	Л5	1Н0
	1П1	П2	П3	П4	1Л6	1Л6

			П2	П3	П4	Л5	Л5	1Н0
	1П1	П2	П3	П4	1Н6	1Л6

			1П2	1П3	Л4	Н0	1Л6	1Л4
	1П1	1П2	1П3	П5	1П5	1Л6

			1П2	1П3	Л4	Л4	1П6	1Н0
	П1	1П2	П3	1Л5	1Л5	1П6

			1П1	1Н0	1П5	Н0	1П6	1Н0
	1П2	1П3	1П4	П4	1Л0	---

			---	1П3	П4	П5	Л6	Л6
	П2	1П2	1П3	П4	П5	Н0

			1П2	1П3	1Л4	1Л5	Л5	Н0
	1П1	П2	1П3	1Л4	1Н6	Л6

			1Н0	П5	1П4	1Н0	1П6	1П1
	П2	1П3	1П3	1П4	П5	1П6

			П2	1П3	1П4	1П5	Л6	Л6
	П1	П2	1П3	1П4	П5	Н0

			1П2	Н0	1П4	1П2	1П6	1Н0
	П1	Л3	1Л3	1П4	1Л6	1Н0

			1П2	П3	---	1Л5	1Н0	1Н0
	1П1	1П2	1П4	1Л6	1Л5	1Л6

			1П2	---	1Н0	1Л5	1П6	1П3
	1П1	1П3	1П4	1П4	1Л5	1П6

			1П2	1Л3	1П4	1Л5	1П6	Н0
	1Л1	1П2	1Л3	1П4	1Л5	1П6

			1П2	---	П4	Л5	Л5	1Н0
	П1	П3	1П3	П4	Л6	1Л6

			1П2	Л5	Л4	1Н0	1Л6	1П0
	1П1	1П3	1П2	Л4	1Л5	Л6

Задание 4.

1. По данному коду N(T) восстановить программу машины Тьюринга.

Выяснить, является ли машина Тьюринга самоприменимой или несамоприменимой.

При составлении N(T) использована следующая кодировка:

П – 1, Л – 1², Н – 1³, - 1⁴, 1 – 1⁵, * - 1⁶, s₀ – 1⁷, s₁ – 1⁸, s₂ – 1⁹.

№	N(T)
1.	18*14*1*19**18*15*1*18**18*16*14*12*18** 19* 14*14*13*19**19*15*15*1*19**19*16*14*1*18
2.	18*14*14*1*17**18*15*16*1*19**16*15*12*19** 19* 14*14*1*18**19*15*15*1*18**19*16*15*1*19
3.	18*14*14*1*18**18*15*16*12*17**18*16**15*13*17** 19* 14*14*13*17**19*15*16*1*19**19*16*16*1*18
4.	18*14*14*12*19**18*15*16*12*18**18*16*15*13*18** 19*14*14*1*19**19*15*16*12*18**19*16*14*1*18
5.	18*14*14*12*17**18*15*16*12*19**18*16*16*13*19** 19*14*14*12*18**19*15*15*12*17**19*16*15*1*19
6.	18*14*14*12*18**18*15*14*13*17**18*16*16*1*17** 19* 14*14*1*17**19*15*15*13*19**19*16*16*1*18
7.	18*14*14*13*19**18*15*14*13*18**18*16*16*1*18** 19* 14*14*12*19**19*15*16*12*18**19*16*14*1*18
8.	18*14*14*13*17**18*15*15*13*19**18*16*16*1*19** 19* 14*14*1*18**19*15*16*13*19**19*16*15*1*18
9.	18*14*14*13*18**18*15*14*1*17**18*16*16*12*17** 19* 14*14*1*17**19*15*14*1*18**19*16*16*1*19
10.	18*14*14*1*19**18*15*14*1*18**18*16*16*12*18** 19* 14*14*12*18**19*15*15*13*17**19*16*14*1*19
11.	18*14*15*1*17**18*15*14*1*19**18*16*16*12*19** 19*1 14*14*12*19**19*15*16*1*19**19*16*15*12*17
12.	18*14*15*1*18**18*15*14*13*17**18*16*16*13*17** 19* 14*16*12*17**19*15*14*1*19**19*16*16*12*18
13.	18*14*15*12*19**18*15*14*12*18**18*16*16*13*18** 19*14*16*13*18**19*15*15*12*18**19*16*14*12*18
14.	18*14*15*12*17**18*15*14*12*19**18*16*14*13*19** 1 19*14*13*19**19*15*16*12*18**19*16*15*12*18
15.	18*14*15*12*18**18*15*14*12*17**18*16*14*1*17** 19*14*16*13*17**19*15*14*13*17**19*16*16*12*18
16.	18*14*15*13*19**18*15*14*12*18**18*16*14*1*18** 19*14*16*1*19**19*15*14*12*19**19*16*14*12*19
17.	18*14*15*13*17**18*15*14*13*19**18*16*14*1*19** 19*14*16*1*18**19*15*15*13*19**19*16*15*12*19
18.	18*14*15*13*18**18*15*15*13*17**18*16*14*12*17** 19*14*16*1*17**19*15*16*13*18**19*16*16*12*17
19.	18*14*15*1*19**18*15*15*13*18**18*16*14*12*18** 19*14*16*12*19**19*15*14*11*18**19*16*14*12*19
20.	18*14*16*1*17**18*15*15*13*19**18*16*14*12*19** 19*14*16*12*18**19*15*14*12*17**19*16*15*1*19
21.	18*14*16*1*18**18*15*15*1*17**18*16*14*13*17** 19*14*15*12*17**19*15*15*12*19**19*16*16*1*18
22.	18*14*16*12*19**18*15*14*1*18**18*16*14*13*18** 19*14*15*13*19**19*15*16*1*18**19*16*14*1*19
23.	18*14*16*12*17**18*15*15*1*19**18*16*15*13*19** 19*14*15*13*18**19*15*16*12*19**19*16*15*1*17
24.	18*14*16*12*18**18*15*15*12*17**18*16*15*1*17** 19*14*15*13*17**19*15*15*12*19**19*16*16*1*19
25.	18*14*16*12*19**18*15*15*12*18**18*16*15*1*18** 19*14*15*1*19**19*15*16*13*18**19*16*14*12*19
26.	18*14*16*13*17**18*15*15*12*19**18*16*15*1*19** 19*14*15*1*18**19*15*14*13*18**19*16*15*13*18
27.	18*14*16*13*18**18*15*16*13*17**18*16*15*12*17** 19*14*15*1*17**19*15*15*1*18**19*16*16*13*17
28.	18*14*16*1*19**18*15*16*13*18**18*16*15*13*18** 19*14*15*12*19**19*15*16*13*17**19*16*14*13*18
29.	18*14*15*1*17**18*15*16*13*19**18*16*15*12*19** 19*14*15*13*18**19*15*15*1*19**19*16*15*1*18
30.	18*14*14*1*18**18*15*16*1*17**18*16*15*13*17** 19*14*14*12*17**19*15*14*1*18**19*16*16*12*17

 

ОБРАЗЕЦ ОФОРМЛЕНИЯ И ВЫПОЛНЕНИЯ ПРАКТИЧЕСКОЙ РАБОТЫ № 2.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

ПРИДНЕПРОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ СТРОИТЕЛЬСТВА И АРХИТЕКТУРЫ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

ПРАКТИЧЕСКАЯ РАБОТА № 2.

Тема: «МАШИНЫ ТЬЮРИНГА»

Выполнил студент группы _____

_____________________________

(Фамилия, имя, отчество)

Дата выполнения _____________

Дата защиты работы __________

Кол-во баллов: ______________

Подпись преподавателя:

Г. Днепропетровск - 2012

Задание 1.

3. Построить машину Тьюринга, применимую ко всем словам в алфавите и переводящую их в слово .

Проверить работу машины Тьюринга над некоторыми словами.

Решение:

1. Опишем работу алгоритма, решающего эту задачу.

Будем обозначать состояния машины Тьюринга числами 0, 1, 2, 3, …, причем 1 – начальное, а 0 – заключительное состояния.

Вначале с помощью команд проходим до конца слова, не изменяя его символов.

Признаком окончания слова будет считывание в первом состоянии.

С помощью команд движемся влево, не изменяя последнего символа.

Если в состоянии 3 считываем a, значит, , нужно стирать все символы слова , кроме последнего. Это можно сделать с помощью команд . Если в состоянии 4 считывается , значит, вся работа проделана, и пора останавливаться с помощью команды .

Если в состоянии 3 считываем символ b, значит, , нужно все символы, кроме x_n, заменять буквами b. Это делаем с помощью команд . Если в состоянии 5 считывается , значит, все символы исходного слова пройдены, можно переходить в состояние 0 с помощью команды .

Запишем программу найденной машины Тьюринга в виде таблицы:

 

	Л2	-	-	Н0	Н0
a	a П1	a Л3	Л4	Л4	b Л5
b	b П1	b Л3	b Л5	Л4	b Л5

 

2. Проверим работу построенной машины Тьюринга над словами abba:

Итак, в слове abba предпоследний символ – b, и все буквы исходного слова, кроме последней, заменены буквой b.

Проверим работу построенной машины Тьюринга над словом bbaaa:

В слове bbaaa предпоследний символ – a, и все буквы исходного слова, кроме последней, заменены пустыми символами .

Итак, проверка сделана, результат работы машины Тьюринга удовлетворяет требованиям, которые ставились в условии задачи.

 

 

Задание 2.

3. Построить машину Тьюринга, вычисляющую числовую функцию .