Абстрактные автоматы. Машины Тьюринга и Поста

В 1936— 1937 гг. независимо друг от друга и почти одновременно с работами А. Черча и С. Клини было дано определение понятия алгоритма американским и английским математиками Э. Постом и А. Тьюрингом. Их подход базируется на определении специальных абстрактных (т. е. существующих не реально, а лишь в воображении) автоматов (машин). Основная мысль при этом заключалась в том, что алгоритмические процессы — это процессы, которые может со­вершать подходяще устроенная «машина». В соответствии с этим ими с помощью точных математических терминов были описаны классы машин, способные осуществить или имитировать все алгоритмиче­ские процессы, когда-либо описываемые математиками [2].

Машины, введенные Постом и Тьюрингом, отличались не очень существенно и в дальнейшем стали называться машинами Тьюринга. В общем случае такая машина состоит из следующих частей

(рис. 5.2):

1) информационной ленты, представляющей собой бесконечную

(неограниченную) память машины. В качестве информационной ленты может служить магнитная или бумажная бесконечная лен­та, разделенная на отдельные ячейки. В каждой ячейке можно по­местить лишь один символ, в том числе и ноль;

2) «считывающей головки» — специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль голов­ки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в одной определенной ячейке ленты;

3) управляющего устройства, которое в каждый рассматрива­емый момент находится в некотором «состоянии». Предполагается, что устройство управления машины может находиться в некото­ром конечном числе состояний. Состояние устройства управления часто называют внутренним состоянием машины. Одно из этих со­стояний называется заключительным и управляет окончанием ра­боты машины.

Машины Тьюринга представляют собой универсальных испол­нителей, с использованием которых можно имитировать все алго­ритмические процессы, описываемые математиками. Доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций.

Таким образом, вопрос о существовании или несуществовании алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или несуществовании машины Тьюринга, обладающей нужным свойством.

В универсальной машине Тьюринга, как и во всякой тьюринговой машине, информация изображается символами, расположенными одновременно на магнитной ленте. При этом универсальная маши­на Тьюринга может располагать лишь фиксированным конечным внешним алфавитом. Между тем она должна быть приспособлена к приему в качестве исходной информации всевозможных состоя­ний устройства управления и конфигураций, в которых могут встре­чаться символы из разнообразных алфавитов со сколь угодно боль­шим числом различных символов.