9.1. Зачем нужны простые вычислительные модели?

До сих пор нам было удобно ссылаться на програм­мистский опыт, говоря об алгоритмах, программах, ин­терпретаторах, пошаговом выполнении и т. д. Это позво­ляло нам игнорировать детали построения тех или иных алгоритмов под тем предлогом, что читатель их легко восстановит (или хотя бы поверит — всё-таки не каждый читатель в своей жизни писал интерпретатор паскаля на паскале).

Но в некоторых случаях этого недостаточно. Пусть, например, мы хотим доказать алгоритмическую неразре­шимость какой-то задачи, в определении которой ничего не говорится о программах (в этом разделе, например, мы докажем неразрешимость проблемы равенства слов в полугруппах, заданных образующими и соотношениями). Это обычно делается так. Мы показываем, что пробле­ма остановки сводится к этой задаче. Для этого мы мо­делируем работу произвольного алгоритма в терминах рассматриваемой задачи (что это значит, будет видно из приводимого ниже примера). При этом нам важно, чтобы определение алгоритма было как можно проще.

Таким образом, наш план таков. Мы опишем довольно просто определяемый класс машин (его можно выбирать по-разному, мы будем использовать так называемые ма­шины Тьюринга), затем объявим, что всякая вычисли­мая функция может быть вычислена на такой машине, а затем покажем, что вопрос об остановке машины Тью­ринга можно свести к вопросу о равенстве слов в полу­группе.

Другая причина, по которой важны простые вычи­слительные модели (таких моделей много — разные ви­ды машин Тьюринга, адресные машины и т.п.), связана с теорией сложности вычислений, когда нас начинает ин­тересовать время выполнения программ. Но этот вопрос выходит за рамки классической теории алгоритмов.

Машины Тьюринга: определение