Новый ум короля: О компьютерах, мышлении и законах физики | страница 67

_>8 , T_>9 и T_>10 . С T_>7 возникают трудности еще более фундаментального характера. Строка нулей и единиц, которой она представляется, включает последовательность из пяти единиц: 110111110. Интерпретации этой последовательности не существует, поэтому T_>7 намертво застревает сразу же, как только доходит до первой единицы. (Я буду называть T_>7 , равно как и любую другую машину T_>n, двоичное расширенное представлений которой содержит более четырех единиц, некорректно определенной.) Машины T_>5, T_>6 и T_>12 испытывают те же трудности, что и T_>0, T_>1, T_>2: они просто никогда не останавливаются. Все эти машины — T_>0, T_>1 , T_>2 , T_>5 , T_>6 , T_>7 , T_>8, T_>9, T_>10 и T_>12 — совершенно бесполезные устройства! Только T_>3 и T_>11 являются функциональными машинами Тьюринга, да и то не слишком интересными. Причем T_>11 даже скромнее, чем T_>3 : натолкнувшись на первую же единицу, она останавливается и вообще ничего не меняет!

Надо заметить, что наш перечень содержит избыточную информацию. Машина T_>12 идентична T_>6, а по действиям обе они аналогичны T_>0, поскольку ни T_>6, ни T_>12 никогда не переходят во внутреннее состояние 1. Но нам нет нужды волноваться из-за этой избыточности, равно как из-за изобилия неработоспособных (фиктивных) машин Тьюринга в нашем списке. На самом деле, мы могли бы изменить систему кодирования таким образом, чтобы избавиться от большого числа бесполезных устройств и значительно уменьшить избыточность списка машин. Но все это можно сделать только ценой усложнения нашей примитивной универсальной машины Тьюринга, которая должна расшифровывать вводимую в нее запись и имитировать машину T_>n, чей номер она считала. Это было бы оправдано, если бы было можно избавиться от всех бесполезных (и повторяющихся) машин. Но это, как мы увидим чуть позднее, невозможно! Поэтому мы оставим нашу систему кодирования без изменений.

Будет удобно интерпретировать ленту с последовательностью меток на ней, например

…0001101110010000…,

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

110111001,

как двоичное представление натурального числа (в десятичной форме это 441). Однако такая процедура даст нам только нечетные числа (их двоичное представление оканчивается на