Жар холодных числ и пафос бесстрастной логики

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

Предполагается, что машина Тьюринга реагирует на знаки из некоторого набора знаков — внешнего алфавита, наносимые в ячейках некоторой (бумажной или иной) ленты; в каждой ячейке может быть нанесен только один знак;

если знак в ячейке отсутствует, считается, что в ней нанесен пустой знак (ячейка с таким знаком называется пустот машина не реагирует ни на какие другие знаки (предпо. латается, что ей никто и не «показывает» других знаков, чтобы не ставить ее в затруднительное положение).

Это предположение тоже естественно. Почтовый автомат который в наши дни расшифровывает написанный по определенному стандарту индекс отделения связи, служит примером того, как несложный механизм может выполнять про. цедуру «опознавания» простых начертаний.

Набор действий, доступных машине Тьюринга, весьма ограничен. Она может выполнить следующие операции:

(1) перейти в другое внутреннее состояние (или остаться в прежнем состоянии);

(2) стереть знак, напечатанный в обозреваемой ею ячейке ленты, напечатать вместо него другой или оставить знак без изменения;

(3) передвинуть бумажную ленту на стандартное расстояние (скажем, на 1 см), соответствующее размеру ячейки, в левую или в правую сторону;

(4) остановиться (например, отключиться от сети, если она электрическая); остановку машины можно понимать как ее переход в особое — заключительное — состояние.

Больше ничего машина Тьюринга делать не способна.

Перед началом работы машины Тьюринга на ее ленту каким-либо образом наносятся знаки из внешнего алфавита; образующиеся в результате этого конфигурации знаков следует рассматривать как исходную информацию, подлежащую переработке данной машиной. Машина обладает активным органом: считывающе-записывающей головкой, которая перед началом работы устанавливается ровно против одной из ячеек ленты. Про эту ячейку тогда говорят, что она обозревается машиной. Работа машины — изменение ею конфигурации знаков на ленте, обозревание все новых и новых (в общем случае) ячеек и переход из одного состояния в другое — происходит в дискретном времени: по тактам. На каждом из них ее поведение определяется двумя факторами — знаком, воспринимаемым на обозреваемой ячейке, и внутренним состоянием машины. Само же поведение складывается из двух действий; одно из них соответствует пункту (2) или (3), другое — пункту (1) или (4). Если, действуя в соответствии с пунктом (3), машина сдвинет ленту до самого ее конца, то считается, что она включает некое устройство подклейки нового куска ленты. Таким образом, лента машины мыслится потенциально бесконечной в обе стороны, в чем состоит существенная связанная с этой машиной идеализацией, именно поэтому машину Тьюринга называют абстрактной машиной.

В том, что каждое действие машины строго однозначно определяется ее внутренним состоянием и тем знаком, который она обозревает, состоит жесткая детерминистичность ее поведения. Однако эта детерминистичность, так сказать, минимальна: только два фактора влияют на ее поведение да каждом такте работы — текущее внутреннее состояние и воспринимаемый знак на ленте — и оно не зависит от истории машины: от ее прошлых состояний. Иными словами, машина Тьюринга ничего не помнит. В этом отношении ее поведение является воплощением «механичности», «слепого автоматизма».