Доказательство. 3 страница

· бесконечной ленты, разделенной на ячейки, которая используется для ввода и вывода данных, а также для записи промежуточных результатов. На ленте могут записываться буквы некоторого алфавита А={a₀,a₁,…a_m} (внешний алфавит машины Тьюринга). Удобно считать, что пустые ячейки на самом деле содержат некоторую букву алфавита А (будем считать для определенности, что это буква a₀.)

· управляющей головки, способной читать символы, содержащиеся в ячейках ленты, писать символы в эти ячейки и оставаться на месте или передвигаться на одну ячейку вправо или влево.

· выделенной ячейки памяти, содержащей символ внутреннего алфавита, задающий состояние машины Тьюринга. Головка может находиться в одном из состояний Q={q₀,q₁…q_n} (внутренний алфавит машины Тьюринга). Состояние q₀ – заключительное, q₁ – начальное.

· механического устройства управления, обеспечивающего перемещение головки относительно ленты

· функциональной схемы — области памяти, содержащей команды (программу) машины Тьюринга, доступной только по чтению

Обычно машина Тьюринга схематично изображается так

aj1

aj2

ajk

ajr

Поскольку бесконечную ленту физически представить затруднительно, обычно предполагается, что она конечная и разбита на конечное число ячеек. В процессе работы к существующим ячейкам машина может пристраивать новые ячейки, так что лента может считаться потенциально неограниченной в обе стороны. Все вновь пристраиваемые ячейки пристраиваются пустыми. Без ограничения общности ленту можно считать бесконечной лишь с одной стороны. Тогда ленту можно считать направленной и ее ячейки удобно просматривать слева направо.

Управляющая головка – это некоторое устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится в определенной ячейке ленты. Если какая-нибудь ячейка находится в управляющей головке, то говорят также, что машина в данный момент «воспринимает» или «обозревает» эту ячейку.

Внутренняя память машины – это некоторое устройство, которое в каждый рассматриваемый момент находится в некотором «состоянии». Предполагается, что число возможных состояний внутренней памяти конечное и для каждой машины фиксированное. Состояние внутренней памяти мы будем обозначать символами алфавита Q={q₀,q₁…q_n} или любыми другими символами, не входящими во внешний алфавит машины. Совокупность символов, обозначающих состояния внутренней памяти, называется внутренним алфавитом машины. Состояния внутренней памяти часто называют внутренними состояниями машины. Одно из этих состояний называется начальным, с него начинает работу любая машина, пусть это будет состояние q₁. Еще одно специальное состояние q₀ - заключительное. Символ, обозначающий заключительное состояние, будет называться стоп-символом. Наконец, если в какой-то момент времени внутренняя память машины приходит в заключительное состояние q₀, то дальнейших изменений в машине не происходит и машина называется остановившейся. Может случиться, что в машине не будет происходить никаких изменений и при каком-то другом внутреннем состоянии q_i. Однако в этом случае мы будем говорить, что машина продолжает работать «вечно».

Предполагается, что машина снабжена особым механизмом, который в зависимости от состояния воспринимаемой ячейки и состояния внутренней памяти может изменить состояние внутренней памяти и одновременно изменить состояние воспринимаемой ячейки и сдвинуть управляющую головку в соседнюю ячейку. В частном случае состояние воспринимаемой ячейки и/или состояние внутренней памяти могут оставаться неизменными, а управляющая головка – неподвижной. Если управляющая головка находится в самой правой ячейке и по ходу работы машина должна сдвинуть управляющую головку в соседнюю справа (отсутствующую) ячейку, то предполагается, что, сдвигая головку, машина одновременно пристроит недостающую ячейку в пустом состоянии. Аналогично работает машина и в случае, когда головка воспринимает самую левую ячейку и по ходу дела машине надо сдвинуть головку еще левее.

Работа машины состоит в том, что она из данного «состояния» по истечении одного такта работы механического устройства переходит в следующее «состояние», затем от нового состояния по истечении такта работы переходит к новому состоянию и так далее. Таким образом, если машина, имея внутреннее состояние q_i и воспринимая ячейку ленты с символом a_i переводит внутреннюю память в состояние q_b и одновременно содержимое воспринимаемой ячейки заменяет символом a_s, а управляющая головка остается на месте (H), сдвинется на одну ячейку вправо (R) или влево (L), то говорят, что машина выполняет команду соответственно

q_i a_i→a_s H q_b,

q_i a_i→a_s R q_b,

q_i a_i→a_s L q_b.

Совокупность всех команд, которые может выполнять машина, называется ее программой. Так как работа машины по условию целиком определяется состоянием в данный момент ее внутренней памяти q_i и состоянием воспринимаемой ячейки a_j, то для каждых q_i a_j (i=1, …, n; j=0, 1, …, m), программа машины должна содержать одну и только одну команду, начинающуюся словом q_i a_j. Таким образом, программа машина с символами{ a₀, a₁, …, a_m } и состояниями { q₀,q₁…q_n } содержит максимум (n+1)(m + 1) команд. При этом некоторые команды являются «мертвыми», в том случае, если ни при каких входных словах в данном алфавите невозможно наступление этой конфигурации. В грамотной с точки зрения реализации программе таких строк быть не должно, хотя формально их наличие ошибкой не является.

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

· левее слова х и правееслова у все ячейки содержат пустой символ,

· головка машины обозревает ячейку, которая находится сразу после слова х,

· первая буква слова у записана в ячейке ленты, обозреваемой головкой машины,

· q_i – состояние машины на данном шаге.

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

a0

a0

a0

a0

a0

a0

a0

Конфигурация с начальным состоянием головки называется начальной, с заключительным состоянием – заключительной. Переход за один такт работы МТ из конфигурации x₁ q_i y₁ в конфигурацию x₂ q_j y₂ будем обозначать так

x₁ q_i y₁ ￄ x₂ q_j y₂

Если переход из одной конфигурации в другую осуществляется более, чем за один шаг, то это будем обозначать таким образом

x₁ q_i y₁ ￂ x₂ q_j y₂

Действия МТ весьма разнообразны и зависят не только от программы, но и от начальной записи на ленте и начального положения головки. Любые действия машины можно назвать вычислениями.

Вычисления, производимые МТ в алфавите А – правильные, если выполняются следующие условия

· В начальный момент машина находится в состоянии q₁.. а ленте записано некоторое слово W в алфавите А и все ячейки ленты, не содержащие слово W, содержат пустой символ. Головка машины обозревает ячейку с первой буквой слова W.

a0

a0

a0

a0

a0

a0

a0

· При переходе МТ в заключительное состояние q₀ все ячейки левее головки содержат пустой символ. Головка находится над самой левой среди ячеек, не содержащей пустой символ (если такие имеются).

Результатом правильных вычислений МТ считается:

· Пустое слово, если ячейки ленты не содержат непустых символов.

· Слово, первая буква, которого находится в ячейке, обозреваемого головкой, а последняя отлична от пустого символа и такая, что все буквы на ленте являются пустыми символами.

Пример 1. Построить МТ, которая осуществляет переход 0 q₁ 1 ⁿ ￂ01 ⁿ q₀ 0.

Нетрудно понять, что внешний алфавит для такой МТ достаточно взять двухсимвольный А={0,1}, причем пустым символом будет 0.

Действия МТ в данном случае сводятся к переходу к первому нулю после последовательности единиц и остановке.

Программа МТ для перехода

q₁0®0Hq₀

q₁1®1Rq₂

q₂1®1Rq₂

q₂0®0Hq₀

Удобно представлять программу МТ в виде таблицы, строки которой помечены символами внешнего алфавита МТ, а столбцы – символами внутреннего алфавита МТ. Если МТ имеет команду q_i a_i→a_s H q_b, то в ячейке на пересечении строки a_i и столбца q_i находится выражение a_s H q_{b .} Заполним таблицу, которая соответствует данной МТ.

	q1	q2
0	0Hq0	0Hq0
1	1Rq2	1Rq2

Приведем пошаговое исполнение программы для начальной конфигурации при n =3.

0 q₁ 1 1 1 0ￄ 0 1 q₂ 1 1 ￄ 0 1 1 q₂ 1 0 ￄ 0 1 1 1 q₂ 0 ￄ0 1 1 1 q₀ 0

Пример 2. Построим МТ, которая работает следующим образом (x,у ³1)

q11x01yÞ	0q0 10, если x³у
0q0 0, если x<y

Внешний алфавит для такой МТ достаточно взять двухсимвольный А={0,1}, причем пустым символом будет 0. Будем удалять из каждой группы единиц по одной единице до тех пор, пока одна из групп не станет пустой, причем из первой группы будем удалять из начала, а из второй из конца. Тогда если пустой стала первая группа единиц, то x<y и необходимо обнулить все оставшиеся единицы и остановиться в заключительном состоянии. Если пустой стала вторая группа единиц, то x³у и необходимо обнулить все оставшиеся единицы, поставить одну единицу и остановиться в заключительном состоянии. Программа такой МТ имеет следующий вид

q11®0Rq2	Удаляем 1 из начала первой группы
q21®1q2R	Проходим через первую группу единиц вправо
q20®0q3R	Проходим через разделяющий 0 вправо
q31®1q3R	Проходим через вторую группу единиц вправо
q30®0q4L	Устанавливаем головку на конец второй группы единиц
q41®0q5L	Удаляем 1 из конца второй группы
q51®1q5L	Проходим через вторую группу единиц влево
q50®0q6L	Проходим через разделяющий 0 влево
q61®1q6L	Проходим через первую группу единиц влево
q60®0q1R	Устанавливаем головку на начало первой группы единиц и повторяем все действия
q10®0q8R	Если первая группа закончилась, удаляем оставшиеся единицы
q81®0q8R	Проходим через вторую группу единиц вправо, заменяя 1 на 0
q80®0q8H	Остановка
q40®0q7L	Если вторая группа закончилась, удаляем оставшиеся единицы
q71®0q7L	Проходим через первую группу единиц влево, заменяя 1 на 0
q70®1q0H	Остановка на ячейке с единицей

Приведем пошаговое исполнение программы для начальной конфигурации при х =3, у =2.

0 q₁ 1 1 1 0 1 1 0ￄ00 q₂ 1 1 0 1 1 0 ￄ 0 1 q₂ 1 0 1 1 0ￄ 0 1 1 q₂ 0 1 1 0ￄ

0 1 1 0 q₃ 1 1 0ￄ 0 1 1 0 1 q₃ 1 0 ￄ 0 1 1 0 1 1 q₃ 0 ￄ 0 1 1 0 1 q₄ 10 ￄ

0 1 1 0 q₅ 10 ￄ 0 1 1 q₅ 0 1 0 ￄ 0 1 q₆ 1 0 1 0 ￄ 0 q₆ 1 1 0 1 0 ￄ q₆ 0 1 1 0 1 0 ￄ

0 q₁ 1 1 0 1 0 ￄ 0 q₂ 1 0 1 0 ￄ 0 1 q₂ 0 1 0 ￄ 0 1 0 q₃ 1 0 ￄ0 1 0 1 q₃ 0 ￄ0 1 0 q₄ 1 0 ￄ

0 1 q₅ 0 0 0 ￄ0 q₆ 1 0 0 0 ￄ0 q₆ 1 0 0 0 ￄ q₆ 0 1 0 0 0 ￄ0 q₁ 1 0 0 0 ￄ0 q₂ 0 0 0 ￄ

0 q₃ 0 0 0 ￄ0 q₄ 0 0 0 ￄ0 q₇ 0 0 0 ￄ0 q₀ 1 0 0

2.3 Вычисление функций на машине Тьюринга

Далее будем применять МТ для правильного вычисления арифметических функций f: N ® N. Для вычисления f(х), х=0,1,…, будем представлять х в виде последовательности х+1 единиц. Если функция зависит от нескольких переменных, то, введя дополнительный символ (разделитель *) во внешний алфавит, будем последовательно записывать последовательности единиц, соответствующие аргументам функции, разделенные символом разделителем.

Правильным вычислением арифметической функции f(х), х=0,1,…, на МТ будем называть правильные вычисления, производимые МТ в алфавите А ={0,1} при переходе от конфигурации 0 q₁ 1 ^x+1 0к конфигурации 0 q₀ 1 ^f(x)+1 0.

Пример. Вычислим функцию O(x)= 0.

Очевидно, что действия МТ сводятся к последовательной замене всех единиц на ленте нулями.

Программа вычислений

	q1	q2
0		1Hq0
1	0Rq2	0Rq2

Пример. Вычислим функцию S(x)=x+1

Для вычисления этой функции достаточно приписать слева одну единицу к последовательности единиц на ленте.

Программа вычислений

	q1	q2
0		1Hq0
1	1Lq2

Пример. Построить машину Тьюринга для вычисления функции C(x)=S(O(x)).

Искомую машину будем строить как суперпозицию машин, вычисляющих функции O(x)= 0 и S(x)=x+1 Возьмем МТ, вычисляющие эти функции. Объединим состояния и программы этих машин. Пусть имеются две машины Т₁ и Т₂, которые вычисляют функции f₁(x) и f₂(x) соответственно в одном и том же алфавите. Построим новую машину Тьюринга Т следующим образом. Состояния машины Т₂ переобозначим так, чтобы они отличались от состояний Т₁. Начальное состояние q₁¹ машины Т₁ объявляем начальным состоянием q₁ машины Т. Заключительное состояние q₀² машины Т₂ объявляем заключительным состоянием q₀ для машины Т. Заключительное состояние q₀¹ машины Т₁ и начальное состояние q₁² машины Т₂ отождествляем. Полученные команды для обеих машин объединяем в одну программу новой машины. Построенная машина Т вычисляет суперпозицию функций f(x)=f₂(f₁(x)) и называется суперпозицией машин Т₁ и Т₂.

В результате из двух таблиц

	q1	q2			q1	q2
0		1Hq0		0		1Hq0
1	0Rq2	0Rq2		1	1Lq2

получим одну

	q1	q2 1	q0 1	q22
0		1H q01		1Hq0
1	0R q2 1	0R q2 1	1L q22

Пример. Построить МТ для вычисления функции

Ранее были построены МТ для вычисления функций O(x)= 0 и S(x)=x+1. Легко видеть, что исходная функция – это функция O(x), если x> 1 и функция S(x) в противном случае. Таким образом, перед вычислением нужно определить сколько единиц находится на ленте, и в зависимости от этого переходить к вычислению функций. Для определения количества единиц на ленте будем сдвигаться по ленте вправо и на каждом сдвиге менять состояние МТ. Если обнаружили больше двух единиц, необходимо вернуться назад на начало последовательности единиц и применить МТ для вычисления функции O(x). Если обнаружили две или одну единицу, то устанавливаем головку на начале последовательности единиц и применяем МТ для вычисления функции S(x). Внутренние состояния машин для вычисления функций O(x) и S(x) пометим буквами O и S соответственно. Заключительные состояния этих машин отождествим.

q₁1®1Rq₂

q₂1®1Rq₃ На ленте больше одной единицы

q₃1®1Lq₄ На ленте больше двух единиц

q₄1®1Lq₄

Сдвигаемся обратно на начало последовательности

q₄0®0Rq_О0 Начинаем вычисление функции O(x)

q₂0®0Lq_S0 На ленте одна единица, начинаем вычисление S(x)

q₃0®0Lq₅

На ленте две единицы, переходим на начало последовательности

q₅1®1Lq₅

q₅0®0Rq_S0 начинаем вычисление S(x)

Пример. Построить МТ для вычисления функции

Чтобы правильно вычислить данную функцию, необходимо построить МТ, которая переводит конфигурацию 0 q₁ 1 ^x+1 01 ^y+1 в конфигурацию 0 q₀ 1 ^x+y+1 0

Порядок действий для МТ можно выбрать такой. Сначала происходит движение головки вправо до появления на ленте нуля. Этот нуль разделяет аргументы на ленте. Поставим в эту ячейку вместо нуля единицу и вернемся к началу последовательности единиц. Заменим первые две единицы нулями. Тогда на ленте останется единиц.

Набор команд для такой МТ

q₁1®1Rq₂

q₂1®1Rq₂

q₂0®1Lq₃

q₃1®1Lq₃

q₃0®0Rq₄

q₄1®0Rq₅

q₅1®0Rq₀

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

Проверим работу МТ для конкретных значений переменных

Последовательно применим команды МТ для данной конфигурации

0 q₁ 11110111ￄ01 q₂ 1110111ￄ011 q₂ 110111ￄ0111 q₂ 10111ￄ01111 q₂ 0111

ￄ0111 q₃ 11111ￄ011 q₃ 111111ￄ01 q₃ 1111111ￄ0 q₃ 11111111ￄ q₃ 011111111

ￄ0 q₄ 11111111ￄ00 q₅ 1111111ￄ000 q₀ 111111

Таким образом, головка МТ остановилась в заключительном состоянии на самой левой единицы последовательности из 6 (3+2+1) единиц Функция вычислена правильно.

2.4 Алгоритмически неразрешимые задачи

Согласно Тьюрингу алгоритм решения задачи – это машина Тьюринга для вычисления подходящей арифметической функции. Если машина Тьюринга существует для решения задачи, то такая задача называется алгоритмически разрешимой, в противном случае задача алгоритмически неразрешима. В этом разделе будет показано существование алгоритмически неразрешимых задач, т.е. таких задач для которых не существует машины Тьюринга.

Предварительно пронумеруем все машины Тьюринга следующим образом. Зафиксируем счетные множества символов и . Будем считать, что внешние алфавиты всех МТ берутся из множества , при этом символ принадлежит всем внешним алфавитам МТ и интерпретируется как пустой символ. Символы внутренних алфавитов всех МТ берутся из множества , а символы и принадлежат внутренним алфавитам всех МТ и интерпретируются как начальное и заключительное состояния соответственно.

Каждому символу из множества поставим в соответствие двоичную последовательность по следующему правилу

R
L
H
	102i+4
	102i+5

Очевидно, что последовательности и могут совпадать только тогда, когда .

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