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

В 30-е гг. для анализа вычислимости Алан Тьюринг и Эмиль Пост предложили свои идеи абстрактных вычислительных устройств, которые являются точной моделью того, что способно делать любое физическое вычислительное устройство. С помощью этих моделей были найдены примеры алгоритмически неразрешимых задач: для этих задач не существует общего правила их решения при помощи последовательности шагов. Например, нельзя написать программу, которая примет на вход другую программу и выведет, остановится ли эта программа, если ее запустить. Можно привести пример: если бы такая программа существовала, то ей на вход мы могли бы подать алгоритм перебора всех натуральных $x, y, z$, для которых $x^3 + y^3 = z^3$, и решить вопрос великой теоремы Ферма. Подобные утверждения требуют логического анализа и не могут быть разрешены при помощи общего алгоритма. И вообще, исчисление предикатов неразрешимо, то есть не существует общего алгоритма, проверяющего произвольную формулу логики предикатов на истинность. Если бы такой алгоритм существовал, то с его помощью мы могли бы без самостоятельного проведения доказательства проверить любое математическое утверждение на истинность.

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

Алгоритм получает на вход объект, что-то с ним делает и выдает выход, т.е. вычисляет некоторую функцию. Это не просто функция, а процедура, которая имеет конечное описание. Все данные записаны конечным набором символов. Сразу отметим, что количество конечных слов в алфавите $A$ счетно: $\mathbb N \cup \mathbb N^2 \cup \mathbb N^3 \cup \dots \cup \mathbb N^k \cup \ldots \sim \mathbb N$. Действительно, все пары натуральных чисел можно пронумеровать, это называется канторовской нумерацией. А нумерация строк называется геделевской нумерацией.

Алгоритм:

• конечная инструкция, применяемая одинаково ко всем входам;

• вход и выход – конечные объекты;

• выполнение производится пошагово (дискретное время).

Чтобы задать машину Тьюринга, нужно определить следующие объекты:

• алфавит ленты $A = {a_0, a_1, a_2, \ldots, a_m}$, состоящий из символов, которые могут появиться на ленте;

• алфавит состояний $Q = {q_0, q_1, \dots, q_n}$ конечного автомата, при этом $q_1$ – начальное состояние, $q_0$ – конечное состояние;

• $\delta \colon Q \setminus {q_0} \times A \to Q \times A \times {\mathtt{L,R,N}}$ – функция переходов, которая задает команды машины Тьюринга такого вида: $q_i a_j \to q_k a_l X$, где $X \in {\mathtt{L,R,N}}$ – направление движения управляющего устройства по ленте.

Если машина находится в состоянии $q_i$ и видит символ $a_j$, то она переходит в состояние $q_k$ и записывает символ $a_l$, и двигается влево, вправо или остается на месте.

Можно ограничиться рассмотрением функций над числовыми множествами, потому что любую информацию можно представить в цифровом виде. Будем говорить, что машина Тьюринга вычисляет частичную функцию $f \colon D \subset \mathbb N_0 \to \mathbb N_0$, если:

• если $x \in D$ подан на вход, то машина останавливается и выдает $f(x)$;

• если $x \notin D$, то машина не останавливается.

Машина Тьюринга – это конечный объект, таких объектов счетное множество. В то же время, всевозможных функций, действующих из $\mathbb N$ в $\mathbb N$ столько же, сколько бесконечных числовых последовательностей – столько, сколько вещественных чисел, так что мощность множества функций ($\mathbb R$) превосходит мощность множества алгоритмов. Значит, на все функции алгоритмов не хватит, и значит, существуют невычислимые функции.

Что понимать под вычислением на машине Тьюринга? Дадим определение конфигурации машины. Конфигурация – это полное описание всего, что происходит в машине: в каком она состоянии, куда указывает управляющее устройство и что написано на ленте. Конфигурация: $MqaN$, где $q \in Q$ – текущее состояние машины, $a \in A$ – элемент алфавита (на который указывает машина), $M, N \in A^*$ – конечные слова (цепочки символов алфавита $A$): перед символом $a$ записано слово $M$, а после него – слово $N$.

Часто в качестве алфавита используют двоичное кодирование и еще добавляют пустой символ, который можно обозначить $#$. Число можно представить в унарном виде: написать на ленте столько единиц, чему равно кодируемое число, или на одну единицу больше (тогда ноль будет кодироваться одной единицей).

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

Литература

Онлайн курс МФТИ по математической логике на платформе Открытое образование

Хопкрофт, Мотвани, Ульман – Введение в теорию автоматов, языков и вычислений – С. 319

Игошин – Теория алгоритмов (2016)