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