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

Эта гипотеза получила название тезиса Тьюринга. Как и тезис Черча, ее нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением машины Тьюринга.

В принципе, эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.

Контрольные вопросы и задания

Пример 4.4.

Пример А.7

Понятие математической модели

Общая идея моделирования

Вернуться в оглавление: Теоретические основы информатики