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