|
В том, что каждое действие машины строго однозначно определяется ее внутренним состоянием и тем знаком, который она обозревает, состоит жесткая детерминистичность ее поведения. Однако эта детерминистичность, так сказать, минимальна: только два фактора влияют на ее поведение да каждом такте работы – текущее внутреннее состояние и воспринимаемый знак на ленте – и оно не зависит от истории машины: от ее прошлых состояний. Иными словами, машина Тьюринга ничего не помнит. В этом отношении ее поведение является воплощением «механичности», «слепого автоматизма». Представим себе, что на ячейках ленты нанесено какое‑то (конечное) число непустых знаков, машина приведена в некоторое исходное внутреннее состояние и нацелена на самый левый непустой знак ленты. Проследим, как может развиваться работа машины. Распознав показанный ей знак, машина произведет элементарное действие, которое определяется этим знаком и ее внутренним состоянием. Возможно, этим действием будет остановка машины. Тогда конфигурация, начертанная на ленте, останется без изменений. Возможно, что она сотрет знак и напишет на этом месте другой знак. Возможно, что при этом она перейдет еще и в новое внутреннее состояние. Тогда на следующей фазе работы она будет обозревать (старый или новый) знак уже в новом состоянии и, следовательно, в общем случае выполнит другое действие. Машина, наконец, может остановиться; если это произойдет, то считается, что напечатанная на ленте конфигурация есть результат переработки машиной первоначальной конфигурации. Но машина может и не остановиться, а работать неограниченно долго. В этом случае считается, что процесс переработки исходной конфигурации не дает результата. Весь описанный сейчас процесс вполне механичен и на всех своих этапах элементарно прост, обозрим и ясен. Но насколько богаты возможности машины Тьюринга, сколь широкий круг преобразований могут выполнять подобные машины? Ответ на этот вопрос дает тезис Тьюринга. Вот его возможная формулировка: «Вычислимым является тот, и только тот, объект, который может быть получен с помощью некоторой машины Тьюринга». На этот раз объектами – и теми, которые задаются в качестве исходных, и теми, которые вычисляются, являются непосредственно уже не числа, а некоторые слова: конфигурации из стандартных символов, или знаков некоторого алфавита. Но что препятствует отождествлять числа с их знаковыми кодами – с их записью, например, в обычной системе счисления или со словами из вертикальных палочек? Такой подход тем более естествен, что речь идет о передаче вычислительных операций машине, которая «понимает» только знаки. Машина Тьюринга может перерабатывать слова, являющиеся кодами чисел, в частности, осуществлять операции, выполняемые рекурсивными функциями, принятыми за исходные, следовательно, может успешно работать в качестве «арифметической машины». — 97 —
|