Машины Тьюринга
Рассмотрим еще один способ определения вычислимых функций, следуя в изложении [29, стр. 12-14]. Формулировка, выраженная в терминах воображаемой вычислительной машины, была дана английским математиком Аланом Тьюрингом в 1936 г. [4]. Главная трудность при нахождении этого определения была в том, что Тьюринг искал его до создания реальных цифровых вычислительных машин. Познание шло от абстрактного к конкретному: фон Нейман был знаком с работой Тьюринга, и сам Тьюринг позднее сыграл вдохновляющую роль в развитии вычислительных машин.
На неформальном уровне мы можем описывать машину Тьюринга как некий черный ящик с лентой. Лента разбита на ячейки и каждая ячейка может содержать пустой символ 0, либо непустой символ 1. Лента потенциально бесконечна в обе стороны в том смысле, что мы никогда не придем к ее концу, но в любое время лишь конечное число ячеек может быть непустым. В начале лента содержит числа входа, в конце - число-выход. В промежуточное время лента используется как пространство памяти для вычисления.
Если мы откроем черный ящик, то обнаружим, что он устроен очень просто. В любой момент времени он может обозревать лишь одну ячейку памяти. Устройство содержит конечный список инструкций (или состояний) q0, q1,..., qn. Каждая инструкция может указать два возможных направлений действий; одного нужно придерживаться, если на обозреваемой ячейки ленты находится 0, а другого, - если там находится 1. В любом случае следующее действие может состоять из таких трех типов элементарных шагов:
1) символ (возможно, такой же, как старый) пишется на обозреваемой ячейки ленты, при этом предыдущий символ стирается;
2) лента сдвигается на одну ячейку влево или вправо;
3) указывается следующая инструкция.
Таким образом, список инструкций определяет некоторую функцию перехода, которая по данной инструкции и обозреваемому символу указывает три компоненты того, что нужно делать. Мы можем формализовать эти идеи, взяв в качестве машины Тьюринга эту функцию перехода.
Определение. Машина Тьюринга - это функция M такая, что для некоторого натурального числа n, область определения этой функции есть подмножество множества {0, 1,..., n}´{0, 1}, а область значений есть подмножество множества {0, 1}´{Л, П}´{0, 1, ..., n}.
Например, пусть M(3,1) = <0, Л, 2>. Подразумеваемый смысл этого состоит в том, что как только машина дойдет до инструкции q3, а на обозреваемой ячейки написан символ 1, она должна стереть 1 (оставляя на ячейке 0), передвинуть ленту так, чтобы обозреваемая ячейка стала левая соседняя ячейка от той, которая обозревалась, и перейти к следующей инструкции q2. Если M(3,1) не определено, то как только машина дойдет до инструкции q3, а на обозреваемой ячейки написан символ 1, то машина останавливается. (Это единственный путь остановки вычисления.)
Такая подразумеваемая интерпретация не включена в формальное определение машины Тьюринга, но она мотивирует и подсказывает формулировки всех следующих определений. В частности, можно определить, что означает для машины M передвижение (за один шаг) от одной конфигурации до другой. Нам не нужно здесь давать формальных определений, так как они являются простыми переводами наших неформальных идей.
Входные и выходные данные - это строчки из 1, разделенные 0. Пусть <n> будет строчкой из 1 длины n+1. Тогда
<n1> 0 <n2> 0 ... 0 <nk>
получено комбинацией k строчек из 1, каждая отделена от другой 0.
Наконец, мы можем определить вычислимость.
Определение. Пусть Df Í Nk - область определения k-местной функции f: Df ® N (N - множество натуральных чисел). Функция f называется вычислимой, если существует машина Тьюринга M такая, что как только M начинает с инструкции q0, обозревая самой левый символ строки
<n1> 0 <n2> 0 ... 0 <nk>,
(вся остальная часть ленты пуста), тогда:
· если f(n1, n2,..., nk) определено, то M в конце концов остановится, обозревая самый левый символ строки <f(n1, n2,..., nk)>, при этом часть, находящаяся справа от этой строчки, пустая;
· если f(n1, n2,..., nk) не определено, то M никогда не останавливается.
Заметим, что имеется бесконечное множество машин Тьюринга, для каждой вычислимой функции своя. Более того, для любой вычислимой функции имеется бесконечное множество машин Тьюринга, вычисляющих эту функцию.
Пример 6.3. Построим машину Тьюринга, вычисляющую сумму n1+n2.
Зададим функцию M следующим образом:
M(0, 1) = <1, П, 0>;
M(0, 0) = <1, П, 1>;
M(1, 1) = <1, П, 1>;
M(1, 0) = <0, Л, 2>;
M(2, 1) = <0, Л, 3>;
M(3, 1) = <0, Л, 4>;
M(4, 1) = <1, Л, 4>;
M(4, 0) = <0, П, 5>.
Посмотрим как происходит сложение 1+1. В текущей строке символов обозреваемый символ выделен.
| Номер инструкции | Текущая строка символов | Комментарий |
| 0110110 | прохождение через первое слагаемое | |
| 0110110 | ||
| 0110110 | заполнение промежутка | |
| 0111110 | прохождение через второе слагаемое | |
| 0111110 | ||
| 0111110 | конец второго слагаемого | |
| 0111110 | стирание 1 | |
| 0111100 | стирание второй 1 | |
| 0111000 | движение назад | |
| 0111000 | ||
| 0111000 | ||
| 0111000 | остановка | |
| 0111000 |
Мы должны заметить, что многие детали нашего определения машины Тьюринга до некоторой степени произвольны. Если бы было более одной ленты, то класс вычислимых функций остался бы неименным, хотя некоторые функции могли бы быть вычислены более быстро. Аналогично, мы могли бы допускать больше символов, чем 0 и 1, или же у нас могла бы быть лента бесконечная только в одну сторону от начальной точки вместо имеющихся бесконечной в обоих направлениях. Ни одно из этих изменений не затрагивает класса вычислимых функций. Что действительно существенно в этом определении - это разрешение произвольно большого количества материала для запоминающего устройства и произвольно длинных вычислений.