Машины Тьюринга

Машиной Тьюринга называется пятёрка объектов

T = (A,S,δ,v,μ), где А = {a₁ , a₂ ,..., a_n} —алфавит;

S = {s₀, s₁ ,..., s_m} —множество внутренних состояний, причём s₀ —заключительное, a. s₁ —начальное состояния.

δ: А х S → S — функция перехода;

v : A х S → А — функция выхода;

μ: А х S → {П, Л, Н} — функция управления.

Командой машины Тьюринга называется запись вида a_kz_i, где а_p , D, s_j- значения на наборе (a_kz_i) функций δ,v,μ соответственно.

Программой машины Тьюринга называется набор всех её команд.

Работа машины Тьюринга связана с бесконечной лентой, разбитой на ячейки, причём в каждой ячейке может быть записан один символ некоторого алфавита, причём λ является символом пустой ячейки.

Работа машины Тьюринга над словом α, записанным на ленте, проходит следующим образом:

машина Тьюринга начинает свою работу всегда в состоянии s₁, а её считывающее устройство расположено над первым слева символом слова, записанного на ленте;

считав символ в ячейке, обозреваемой считывающим устройством машины Тьюринга, она печатает в эту ячейку символ, найденный с помощью функции выхода v, двигается вдоль ленты вправо, влево или остаётся на месте, в случае, если функция μ принимает значения П, Л или Н соответственно и переходит в состояние, определяемое с помощью функции перехода δ; при переходе машины Тьюринга в состояние s₀ считают, что она закончила работу над словом а и говорят, что машина Тьюринга применима к слову α.

Если машина Тьюринга при работе над словом а не переходит в состояние s₀, то говорят, что она не применима к слову α.

Конфигурацией машины Тьюринга называется запись α₁^bs_k α₂, где b — символ ячейки, обозреваемой считывающим устройством машины Тьюринга, находящейся в состоянии s_k, a α₁ и α₂ - слова, записанные на ленте соответственно левее и правее символа b.

Кодом машины Тьюринга называется запись набора её команд в алфавите {*,1}, позволяющая однозначно восстанавливать каждую команду.

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

Числовой функцией называется функция вида f: N^k0 → N₀, k∈N.

Изображением набора аргументов (x₁ , x₂ ,..., x_λ) называется запись вида

Числовая функция f(x₁ , x₂ ,..., x_k) называется вычислимой по Тьюрингу, если существует машина Тьюринга, применимая к любому слову вида (*), переводящая его в слово 1^y+1 , где y = f(x₁ , x₂ ,..., x_k).

 

Задание 3.1.1

1. Построить машину Тьюринга, применимую ко всем словам x₁, x₂,..., x_n в алфавите {а,b} и переводящую их в слово α.

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

 

Таблица 3.1.1

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

Пример решения задания 3.1.1

Решить задание 3.1.1 для

α = {х_т, если x_n-1 = а, b^n-1, если x_n-1 = b, (n>1).

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

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

Вначале с помощью команд (a,1)→aП1; (b,1)→bП1 проходим до конца слова, не изменяя его символов.

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

С помощью команд (λ,1)→λЛ2; (a,2)→aЛЗ; (b,2)→bЛЗ движемся влево, не изменяя последнего символа слова.

Если в состоянии 3 считываем символ а, значит, х_n-1 = а, нужно стирать все символы слова а, кроме последнего. Это можно сделать с помощью команд (а,3)→ λЛ4; (a,4)→ λЛ4; (Ь,4)→ λЛ4. Если в состоянии 4 считывается λ, значит, вся работа проделана, и пора останавливаться с помощью команды (λ,4)→λH0

Если в состоянии 3 считываем символ b, значит, х_n-1 = b, нужно все символы, кроме х_n, заменять буквами b. Это делаем с помощью команд (b,3)→b Л5; (a,5)→ b Л5; (b,5)→ b Л5. Если в состоянии 5 считывается λ, значит, все символы исходного слова пройдены, можно переходить в состояние 0 с помощью команды (λ,5) → λH0.

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

Таблица 3.1.1 а

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

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

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

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

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

Задание 3.1.2

1. Построить машину Тьюринга, вычисляющую числовую функцию f(x₁ , x₂ ,..., x_n).

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

Таблица 3.1.2

№	f(x1 , x2 ,..., xn)
1	f(x,y,z) = x+y
2	f(x,y,z) = y+3
3	f(x,y) = {x-y, если x≥y, 0, если x < y}
4	f(x,y,z,w) = 4
5	f(x,y) = (0, если x≥y, 1, если x < y
6	f(x,y,z) =(z - 3, если z≥3, 0, если z < 3
7	f(x,y,z,w) = y+z+1
8	f(x,y,z) = {0, если x = 0, y, если x≠0
9	f(x,y) = {y-x, если x≤y, 0, если x > y}
10	f(x,y) = {2, если y > 1, x, если y≤1}
11	f(x,y,z) =y + 3 + z
12	f(x,y) = {0, если x≠0, y+1, если x=0}
13	f(x,y) = {x, если x - четно , y, если x - нечетно}
14	f(x,y) = {x+y, если x≥0, 0, если x< y}
15	f(x,y,z) = {z+1, если z≠0, 0, если z=0}
16	f(x,y) = {0, если x - четно , 1, если x - нечетно}
17	f(x,y,z) =2y
18	f(x,y,z) = {w, если x=0, 2, если x≠0}
19	f(x,y) = {x-2, если x≥2, 0, если x < 2}
20	f(x,y) =2x+1
21	f(x,y) = {x, если x - четно , 0, если x - нечетно}
22	f(x,y) = {0, если xy=0, x+y, если xy ≠ 0}
23	f(x,y,z) = x+y
24	f(x,y) = {1, если x=0, 0, если x ≠ 0}
25	f(x,y,z,w) = z+w
26	f(x,y) = {y, если x=1, x+2, если x ≠ 1}
27	f(x,y,z) = {x+y, если z≠0, y, если z = 0}
28	f(x,y,z,w) = {z, если x > 1, w, если x≤1}
29	f(x,y,z) = 2z
30	f(x,y) = {5, если x + y >2, 0, если x + y ≤ 2}

Пример решения задания 3.1.2

Решить задание 3.1.2 для f(x,y) = x + 2у.

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

Набор значений аргументов (х,у) изображается словом 1^x+1λ1^y+1.

Аргумент х должен остаться без изменения, этого можно добиться с помощью команды (1,1)→1П1. Когда в первом состоянии встретится символ λ, значит, мы попали на символ, разделяющий изображения аргументов, переходим в состояние 2, а сам символ λ пока оставляем без изменений с помощью команды (λ,1)→λП2.

Далее, набор единиц, изображающий аргументу, проходим до конца. Для этого добавим команды (1,2)→1П2; (λ,2)→λЛЗ.

Теперь с помощью "челночного" алгоритма удвоим количество единиц в блоке, изображающем вторую переменную.

Расширим алфавит, введя метку #. Считая, что k единиц блока продублированы, рассмотрим, как будет дублироваться к +1-я единица. . Заменим очередную единицу из блока, изображающего вторую переменную, меткой # и будем двигаться вправо ((1,3)→#П4; (1,4)→1П4), пока не встретим пустую ячейку, заполним её единицей и пойдём влево ((λ,4)→1Л5; (1,5)→1Л5), пока не встретим метку, заменим её единицей, перейдём к следующему символу слева, вернувшись в состояние 3 ((#,5)→1ЛЗ).

Когда в третьем состоянии считается λ, значит, блок, изображающий вторую переменную, продублирован. Заменим разделяющий символ единицей ((λ,3)→1Л5) и пойдём на начало полученного блока из x + 1 + 1 + 2(y+1) = x + 2y + 4 единиц. Когда в состоянии 5 встретится λ, значит, пора идти вправо, стирать три лишние единицы, ведь для изображения числа х + 2у требуется х + 2у + 1 единиц. Для этого добавим команды (λ,5)→λП6; (1,6)→λП7; (1,7)→λП8; (1,8)→λН0 .

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

В клетках таблицы, помеченных неопределённым символом — можно вписать любые команды, т. к. до их исполнения дело всё равно не дойдёт.

2. Проверим работу алгоритма над изображением набора пе- ременных (0,1), т. е. над словом 1λ11:

Итак, в результате осталось три единицы, которые являются изображением числа 2.

Заметим, что f(0,1) = 0 + 2⋅1 = 2, так что на ленте получено то, что и нужно было получить.