Точное описание класса частично рекурсивных функций вместе с тезисом Черча дает одно их возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Нельзя ли уточнить непосредственно само понятие алгоритма, а затем при его помощи определить и класс вычисляемых функций ?
Это было сделано в 1936-1937 гг Постом и Тьюрингом независимо друг от друга и почти одновременно с работами Черча и Клини. Основная мысль Поста и Тьюринга заключалась в том, что алгоритмические процессы — это процессы, которые может совершать подхлдяще устроенная »машина». В соответствии с этим ими с помощью точных математических терминов были описаны довольно узкие классы машин. На этих машинах оказалось возможным осуществить или имитировать все алгоритммические процессы, которые фактически когда-либо описывались математиками.
Машины, введенные Постом и Тьюрингом, отличались не очень существенно и в дальнейшем стали называться машинами Тьюринга. Рассмотрим алгоритмические системы, представленные этими машинами.
Под машинами Поста и Тьюринга понимается некоторая гипотетическая (условная) машина, состоящая из следующих частей:
1) информационной ленты, представляющей собой бесконечную (неограниченную) память машины. В качестве информационной ленты может служить магнитная или бумажная бесконечная лента, разделенная на отдельные ячейки. В каждой ячейке можно поместить лишь один символ, в том числе и нуль;
2) “считывающей головки”—специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль головки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в одной определенной ячейке ленты;
3) управляющего устройства, которое в каждый рассматриваемый момент находится в некотором “состоянии”. Предполагается, что устройство управления машины может находиться в некотором конечном числе состояний. Состояние устройства управления часто называют внутренним состоянием машины. Одно из этих состояний называется заключительным и в работе машины играет особую роль, так как оно управляет окончанием работы машины.
Рассмотрим теперь алгоритмическую систему, предложенную Постом.
В алгоритмической системе Поста информация представляется в двоичном алфавите А = {1, 0}.
Таким образом, в каждой ячейке информационной ленты можно поместить либо 0, либо 1. Алгоритм представляется в виде конечного упорядоченного набора правил, называемых приказами. Работа алгоритма начинается с некоторой начальной ячейки, соответствующей первому приказу алгоритма. Составляющие алгоритм приказы могут принадлежать к одному из 6 приказов, выполняемых устройством управления машины Поста:
1. Записать в рассматриваемую ячейку 1 и перейти к i-му приказу.
2. Записать в рассматриваемую ячейку 0 и перейти к i-му приказу.
3. Сдвинуть ленту вправо на одну ячейку и приступить к выполнению i-го- приказа.
4. Сдвинуть ленту влево на одну ячейку и перейти к выполнению i-го приказа.
5. Если в рассматриваемой ячейке записана 1, то перейти к выполнению 7-го приказа, а если записан 0, то перейти к выполнению 1-го приказа.
6. Окончание работы алгоритма, остановка.
Таким образом, алгоритмическая система Поста представляет собой машину с информационной лентой, содержащей в каждой ячейке либо 0, либо 1; с лентой, перемещающейся влево и вправо вдоль головки; с устройством управления, выполняющим 6 приказов (с внутренними состояниями).
Алгоритмы, составленные из любого конечного числа правил, представленных приказами машины Поста, называются алгоритмами Поста. Доказано, что алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот, любая частично рекурсивная функция может быть представлена алгоритмом системы Поста.
В отличие от машины Поста в каждой ячейке ленты машины ‘Тьюринга может находиться один из символов некоторого конечного алфавита, а устройство управления может быть в одном из конечных состояний. Другими словами, машина Тьюринга, работая в произвольном конечном алфавите, может выполнять некоторое конечное число приказов. При этом машины Тьюринга, как и машины Поста, могут сдвигать ленту на одну ячейку вправо или влево, оставляя содержимое ячеек неизменным, или могут изменять состояние воспринимаемой ячейки, оставляя ленту неподвижной.
Этот список операций можно расширить. Машина Тьюринга называется стандартной, если она при сдвиге ленты может предварительно изменять состояние воспринимаемой ячейки.
На машинах Тьюринга оказалось возможным осуществить или имитировать все алгоритмические процессы, которые когда-либо описывались математиками. Было доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций.
Вопрос о возможности или невозможности разрешающего алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или несуществовании машины Тьюринга, обладающей нужным свойством.
В зависимости от числа используемых лент, их назначения и числа состояний устройства управления определяются различные модификации машин Тьюринга. Рассмотрим основные из них.