Машины Тьюринга
В своей работе 1936 года “О вычислимых числах, с приложением к Entscheidungsproblem ” Алан Тьюринг ввел понятие машин Тьюринга.
Он очень четко представлял, что должна делать машина для вычисления чего-либо. Машины Тьюринга состоят из:
конечного множества Q возможных состояний, потому что любое устройство в фиксированный момент времени может находиться только в одном из конечного числа состояний;
потенциально бесконечной ленты, состоящий из последовательных ячеек, σ1, σ2, σ3, из некоторого конечного алфавита Σ; (Σ может быть любым алфавитом, состоящим из хотя бы двух различных символов. Удобно фиксировать алфавит Σ = {0, 1, b}, то есть бинарный алфавит и символ, обозначающий пустую ячейку. Обычно предполагается, что конечный участок ленты заполнен символами бинарного алфавита, а все остальные ячейки пустые.)
головка чтения/записи в ячейку, обращающаяся к ячейке σh , h ≥ 1, и, наконец,
функция перехода, δ: Q × Σ → Q × Σ × {-1,0,1} (смысл функции перехода состоит в том, что в текущем состоянии, с головкой указывающей на ячейку с символом σh , функция перехода определяет следующее состояние, символ, который надо записать в текущей ячейке, и новую позицию головки, h′ = h + d, где d ∈ {-1,0,1} определяется функцией перехода.)
Линейная природа ленты памяти, в отличие от машин с произвольным доступом к памяти, является ограничением на скорость вычисления, но не мощность машин Тьюринга: любую ячейку памяти можно прочитать, но это может занять больше времени, так как придется двигать головку шаг за шагом вдоль ленты.
Красота машин Тьюринга состоит в том, что это предельно простая модель, которая, в то же время, очень мощная. Машины Тьюринга имеют потенциально бесконечную память, поэтому они могут обрабатывать сколь угодно большие входные данные, например, перемножать два огромных числа, но за один шаг можно прочесть только ограниченное количество информации, например, один символ. Даже до того, как было доказано, что машины Тьюринга и остальные модели вычисления эквивалентны, и до тезиса Черча-Тьюринга, Тьюринг очень убедительно отстаивал свою точку зрения о том, что его машины могут вычислить все те же задачи, что и остальные модели вычисления.
2.1 Универсальные машины Тьюринга
Каждую машину Тьюринга можно однозначно задать ее таблицей переходов: для каждого состояния q, и каждого символа σ, δ(q,σ) содержит новое состояние, новый символ и смещение головки. Эти таблицы переходов могут быть записаны как конечные строки символов, представляющие полный набор инструкций для машины Тьюринга. Далее, эти строки могут быть выписаны в лексикографическом порядке следующим образом: M1, M2, M3, …, где Mi - таблица переходов, т.е. полный набор инструкций (или программа), для машины с номером i.
Тьюринг показал, что можно построить универсальную машину Тьюринга, U, которая может выполнять программу любой другой машины Тьюринга. А именно, для любого i и входного слова w, U будет выполнять ровно то же, что и машина Тьюринга с номером i на входе w, в символьной записи
U(i,w) = Mi(w)
Конструкция универсальной машины Тьюринга позволяет понять одно из важнейших свойств вычислимости: одна машина может выполнять любую программу. И не важно, что нам потребуется вычислить в будущем, одна-единственная машина сможет это сделать. Это свойство важно для конструирования и продажи компьютеров. Один компьютер может исполнять любую программу. Нам не нужно покупать новый компьютер каждый раз, когда нам нужно решить новую задачу. Конечно, в век персональных компьютеров, этот факт настолько очевиден, что оценить его довольно сложно.
2.2 Проблема остановки
Поскольку машины Тьюринга были сконструированы так, чтобы производить все возможные вычисления, то они имеют один недостаток, которого нельзя избежать: некоторые машины на некоторых входных данных не останавливаются. Некоторые машины не останавливаются по глупым причинам, например, мы можем ошибиться в написании программы, и программы зациклится, например, в состоянии 17 с головкой, указывающей на ячейку в которой записана 1, машина останется в состоянии 17, запишет 1, и не сместится. Немного менее глупо, мы можем достичь ячейки, в которой и правее которой ничего не записано, и все же оставаться в том же самом состоянии двигаться по одному шагу вправо до тех пор, пока не встретиться ячейка, в которой записана 1. Обе эти ситуации будут обнаружены и исправлены хорошим компилятором. Однако, рассматривая машину Тьюринга MF , которая на входе “0” систематически ищет первый контрпример к теореме Ферма, и, как только найдет, останавливается и печатает контрпример. Пока недавно Эндрю Вильс не доказал теорему Ферма, все математики мира в течение трех веков были неспособны определить, останавливается ли MF на входе “0”. Теперь мы знаем, что нет.
2.3 Вычислимые функции и перечислимость
Так как машина Тьюринга на некоторых входах может не останавливаться, то мы должны быть очень внимательны, определяя функции, вычислимые машинами Тьюринга. Обозначим за  множество натуральных чисел и рассмотрим машины Тьюринга как частичные функции из  в .
Пусть M – машина Тьюринга, а n – натуральное число. Мы говорим, что лента M содержит число n, если лента M начинается с бинарного представления числа n (начальные нули не обязательны), за которым следуют только пустые клетки.
Если мы запустим машину Тьюринга M на ленте, содержащей n, и она остановится с лентой, содержащей m, то мы говорим, что M вычисляет m на входе n. Если же M на входе n никогда не останавливается, или, когда она останавливается, но на ленте написано не натуральное число (например, когда на ленте есть лидирующие нули или между цифрами есть пустые клетки), тогда мы говорим, что M(n) неопределенно, в символах, M(n) = . Тогда мы можем каждой машине Тьюринга поставить в соответствие частичную функцию M: N → N ∪ {}. Мы говорим, что функция M везде определена, если для всех n∈N, M(n) ∈ N.
Теперь мы можем формально определить рекурсивно перечислимое множество, которое до этого мы определили интуитивно. Пусть S ⊆ N. Тогда S рекурсивно перечислимо, если существует машина Тьюринга, M, такая, что S является образом функции, вычислимой машиной M, в символьной записи,
S = {M(n) | n ∈N; M(n) ≠ } .
Тем самым, S рекурсивно перечислимо, если оно выписывается какой-нибудь машиной Тьюринга. Предположим, что S рекурсивно перечислимо и все его элементы перечислимы машиной M, как описано выше. Затем мы можем описать другую машину Тьюринга P, которая, на входе n, выполняет M параллельно на всех входах, пока на каком-нибудь из входов M не выдаст n. Если это случилось, P останавливается и выдает “1”, то есть, P(n) = 1. Если n ∉ S, то M никогда не выдаст n, то есть P(n) никогда не остановится, то есть P(n)= .
Если машина Тьюринга P на входе n останавливается, то обозначим это как P(n)↓. Определим множество L(P) как множество всех натуральных чисел, на которых P останавливается.
L(P) = {n | P(n)↓} .
Приведенное выше утверждение показывает, что любое рекурсивное множество S есть подмножество натуральных чисел, на которых останавливается какая-нибудь машина Тьюринга P, то есть, S = L(P). Обратное утверждение также верно. Тем самым, S рекурсивно перечислимо тогда и только тогда, когда на нем останавливается какая-нибдуь машина Тьюринга P.
Мы называем множество разрешимым, если и только если существует машина Тьюринга M, останавливающаяся на всех входах и для каждого n определяющая, принадлежит ли n множеству S. Если принадлежит, то она выдает “0”, если не принадлежит – “1”.
Множество S ⊆ N разрешимо, если и только если оно само и его дополнение перечислимы. В этом случае мы можем выписать элементы S и N-S в две отдельные колонки, и, тем самым, понять, принадлежит ли n множеству S: если n в первой колонке, то принадлежит, если во второй – то нет.
Неразрешимость проблемы остановки
Тьюринг был заинтересован следующей проблемой: верно ли, что всякое подмножество натуральных чисел разрешимо. Легко понять, что нет. Действительно, множество подмножеств натуральных чисел несчетно, но, так как множество всех машин Тьюринга счетно, то и множество всех разрешимых множеств счетно. Тем самым, почти все подмножества натуральных чисел неразрешимы.
Тьюринг привел явную конструкцию такого множества. Как мы увидим, он использовал метод, разработанный Кантором для доказательства несчетности множества действительных чисел. Гедель использовал этот же метод для доказательства теоремы неполноты, с помощью которого он построил утверждение J, смысл которого для натуральных чисел моет быть трактован как “J не теорема”.
Тьюринг сконструировал диагональное множество K следующим образом:
K = {n | Mn(n)↓} .
То есть, K состоит из машин Тьюринга, которые останавливаются на своих собственных программах. Легко понять, что K является рекурсивно перечислимым. Пусть дополнение к K также является рекурсивно перечислимым, и d – номер машины Тьюринга, останавливающейся на дополнении к K. То есть, для любого n,
n ∉ K ⇔ Md (n)↓ .
Подставим d вместо n:
d ∉ K ⇔ Md (d)↓ .
По определению d:
d ∈ K ⇔ Md (d)↓ .
Тем самым, мы получаем
d ∈ K ⇔ d ∉ K,
что является противоречием. То есть, наше предположение о том, что дополнение к K перечислимо, ложно, и K не разрешимо. Из этого следует, что не существует алгоритма, который бы по машине Тьюринга и ее входу мог определить, останавливается ли машина на этом входе или нет, и, тем самым, проблема остановки неразрешима.
|
