Моделирование структурированных программ машинами Тьюринга
На первый взгляд могло показаться, что машины Тьюринга с их примитивными элементарными действиями являются более слабыми вычислительными моделями, чем структурированные программы. Но после того, как мы научились реализовывать с их помощью операторы "высокого уровня " - условия и циклы, уже не удивительно, что они позволяют вычислить не меньше, чем структурированные программы.
Теорема 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).
Условие xi = xj реализуется машиной ? =ij, которая, работая на конфигурации (k1, …, ki, …, kj, … , km) выдает 0, если ki=kj, и 1 - в противном случае.
Условие xi < xj реализуется машиной ?<ij, которая, работая на конфигурации (k1, …, ki, …, kj, … , km) выдает 0, если ki < kj, и 1 - в противном случае.
Далее по индукции: пусть ?1 и ?2 - структурированные программы, для которых построены соответствующие машины Тьюринга
программа ?= если ? то ?1 иначе ?2 конец
реализуется машиной M?= if M? then M?1 else M?2 endif, а программа ?= пока ? делай ?1 все реализуется машиной M?= while M? do M?1 enddo.
Используя доказанные выше свойства конструкций машин Тьюринга, нетрудно проверить по индукции следующее
Утверждение 1. Пусть м.Т. M? реализует в соответствии с приведенными определениями структурированную программу ?. Тогда для любого состояния ? программы ? ?(?) = ?1 тогда и только тогда, когда м.Т M?, начав работу в конфигурации K? завершит ее в конфигурации K?1.
Теперь для завершения доказательства теоремы достаточно взять в качестве результирующей следующую м.Т.: M = Mstart; M?; Mend, где м.Т. Mstart переводит одноэтажную начальную конфигурацию
