Введение в схемы, автоматы и алгоритмы
структурированные программы, для которых построены
Условие 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 переводит одноэтажную начальную конфигурацию
