Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
Значение гипотезы для теории алгоритмов: расплывчатое понятие алгоритма отождествляется с точным понятием функциональной схемы МТ.
Обоснование гипотезы
Речь не идет о доказательстве гипотезы, так как она не является точным математическим понятием.
Уверенность в справедливости гипотезы основана главным образом на опыте. Все известные к настоящему времени алгоритмы могут быть заданы посредством тьюринговых функциональных схем. Кроме того, внутри самой теории алгоритмов основная гипотеза не применяется, то есть при доказательстве теорем этой теории ссылок на основную гипотезу не делается.
Вторым доводом в пользу справедливости гипотезы являются теоремы замкнутости и равносильности.
Смысл теорем замкнутости заключается в том, что класс алгоритмов, реализуемых в МТ, замкнут относительно композиции новых алгоритмов из уже имеющихся. Это последовательная и параллельная композиции, разветвление и цикл.
Теоремы равносильности связаны со сравнением различных определений понятия “алгоритм”.
Два алгоритма считаются равносильными, если они решают один и тот же класс задач. Это означает, что при фиксации двух таких классов (К1 и К2) справедливо утверждение:
