|
001: если вы обнаруживаете на ленте 1 и находитесь в состоянии 1, замените 1 на 0, смените ваше внутреннее состояние на состояние 2 и передвиньтесь на один шаг вправо. Подобным же образом, код 010 может означать: 010: если вы обнаруживаете на ленте 0 и находитесь в состоянии 2, передвиньтесь на один шаг влево; а если вы считываете 1, то замените 1 на 0 и передвиньтесь на один шаг вправо. Программная часть ленты может выглядеть как …001010…, если эти две инструкции надо выполнить последовательно. Мы будем называть универсальную машину Тьюринга tu . Заметим, что, в то время как индивидуальная машина Тьюринга считывает только данные, универсальная машина сначала считывает программу, чтобы подготовить себя, а затем уж считывает данные. Так, если мы хотим, чтобы она имитировала t10 , мы считываем программу 10, то есть множество инструкций, настраивающих машину на работу в режиме t10 , а затем скармливаем ей данные. Если данные состоят из числа 3, мы будем ожидать от этого совместного процесса ответ 42 и запишем tu(10,3) = 42 , где первое число в скобках является номером машины Тьюринга, которую мы хотели имитировать, а второе число представляет данные. Предположим теперь, что существует машина Тьюринга, которая может взять программу любой другой машины Тьюринга, например t23 , и любое множество данных, и решить, остановится или нет эта комбинация, чтобы напечатать ответ. Мы назовем эту особую машину Тьюринга th (h здесь от английского глагола «halt» — останавливаться). Если th получает остановку для частной комбинации программы и данных, например t23 и 3, она напечатает 1 и остановится; если она определяет, что комбинация не приводит к остановке, например t22 и 17, th напечатает 0 и остановится. Успех Тьюринга выразился в доказательстве того, что th не включена в список всех возможных машин Тьюринга и поэтому не существует. Чтобы проделать это, он использовал аргументы, очень похожие на «диагональные» аргументы, которыми пользовался Кантор для доказательства того, что иррациональные числа несчетны. Вы можете свободно перейти к следующему подразделу, если хотите пропустить вывод этого результата. Эти аргументы таковы. Предположим, что мы задаем входные данные 0, 1, 2, … и машины Тьюринга t0, t1 , t2 , … и составляем таблицу, верхним левым фрагментом которой является следующая: Вход0123Номер матрицы 0 ????1 3?412 11113 01?2Когда вычисления не останавливаются, мы записываем символ ?. Таблица содержит все возможные вычислимые числа (числа, которые могут быть вычислены машиной Тьюринга до произвольного числа разрядов), поскольку она содержит в своих последовательных рядах все возможные машины Тьюринга, а в последовательных колонках все возможные входы. — 280 —
|