3. Следующее состояние машины (qs).
Совокупность всех команд образует программу машины Тьюринга. Программа представляется в виде двумерной таблицы и называется Тьюринговой функциональной схемой.
a0 a1 a2
q1 a2 л q3 a1 п q2 a2 л q1
q2 a0 н q2 a2 н q1 a1 н q2
q3 a0 п q1 a1 п q4 a2 н q1
q4 a1 н q3 A0 п q4 a2 п q4
Ясно, что работа машины Тьюринга полностью определяется её программой. Ины-ми словами, две машины Тьюринга с общей функциональной схемой неразличимы, и раз-личные машины Тьюринга имеют различные программы.
Основная гипотеза теории алгоритмов.
Машина Тьюринга даёт один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы: насколько общим является понятие машины Тьюринга? Можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является уни-версальным? Может ли всякий алгоритм задаваться таким образом?
На эти вопросы современная теория алгоритмов предлагает ответ в виде следую-щей гипотезы:
Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
Эта гипотеза называется тезисом Тьюринга. Её нельзя доказать, т.к. она связывает нестрогое определение понятия алгоритма со строгим определением понятия машины Тьюринга.
Эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы.
Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.
Напомним также, что другие способы уточнения понятия алгоритма (понятие нор-мального алгоритма А.А.Маркова, понятие рекурсивного алгоритма (рекурсивной функ-ции), введённого Чёрчем, Гёделем и Клини) оказались равносильными.
Этот факт является важным доводом в пользу сформулированной гипотезы.
