структурированные программы, для которых построены
Условие xi = xj реализуется машиной ? =ij, которая, работая на конфигурации (k1, …, ki, …, kj, … , km) выдает 0, если ki=kj, и 1 - в противном случае.
Условие xi < xj реализуется машиной ?<ij, которая, работая на конфигурации (k1, …, ki, …, kj, … , km) выдает 0, если ki < kj, и 1 - в противном случае.
Далее по индукции: пусть ?1 и ?2 - структурированные программы, для которых построены соответствующие машины Тьюринга
и
, а ? - некоторое условие, реализуемое м.Т. M?. Тогда программа ?= ?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 переводит одноэтажную начальную конфигурацию
в m-этажную конфигурацию (x1, x2,…, xn, 0,…, 0), а м.Т. Mend заключительную m-этажную конфигурацию (x1, 0,…, 0) переводит в одноэтажную заключительную конфигурацию |x1.
Содержание Назад Вперед