Введение в схемы, автоматы и алгоритмы
Моделирование структурированных программ машинами Тьюринга
На первый взгляд могло показаться, что машины Тьюринга с их примитивными элементарными действиями являются более слабыми вычислительными моделями, чем структурированные программы. Но после того, как мы научились реализовывать с их помощью операторы "высокого уровня " - условия и циклы, уже не удивительно, что они позволяют вычислить не меньше, чем структурированные программы.
Теорема 10.2. Всякая арифметическая функция, вычислимая некоторой структурированной программой, может быть вычислена также некоторой машиной Тьюринга.
Доказательство Пусть структурированная программа ? вычисляет арифметическую функцию f(x1, …, xn). Не ограничивая общности, будем считать, что Var? ={x1, …, xn, xn+1, …, xm } и что результирующей переменной является x1.
М.Т. M? , моделирующая ?, будет иметь m-этажную ленту с алфавитом ? ={
M? получается с помощью конструкций последовательной композиции, условного оператора и цикла из простых машин Тьюринга, реализующих элементарные присваивания и условия структурированных программ.
Команду xi := 0 (i=1,… , m) программы ? реализует м.Т. Mi0 , обнуляющая i-ый этаж M, т.е. переводящая любую конфигурацию (k1,…, ki-1,ki, k i+1 …, km) в конфигурацию (k1,…, k i-1, 0, ki+1, … , km). Команду xi := xi +1 (i=1,… , m) программы ? реализует м.Т. Mi+1 , добавляющая один символ '|' справа на i-ом этаже, т.е. переводящая любую конфигурацию (k1,…, k i-1, ki, ki+1 … , km) в конфигурацию (k1,…, k i-1, ki+1, ki+1, … , km). Команду xi := xj (i, j=1,… , m) программы ? реализует м.Т. Mij, переписывающая содержимое j-го этажа на i-ый, т.е. переводящая любую конфигурацию (k1,…, ki, …, kj, … , km) в конфигурацию (k1,…, kj, … , kj, … , km).
