Моделирование структурированных программ машинами Тьюринга - часть 2

Условие 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_{\Pi_1}$

$M_{\Pi_2}$

, а ? - некоторое условие, реализуемое м.Т. M?. Тогда программа ?= ?1 ; ?2 реализуется машиной

$M_{\Pi}=M_{\Pi_1};M_{\Pi_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 переводит одноэтажную начальную конфигурацию

$|^{x_1}*|^{x_2}*\ldots |^{x_n}$

в m-этажную конфигурацию (x1, x2,…, xn, 0,…, 0), а м.Т. Mend заключительную m-этажную конфигурацию (x1, 0,…, 0) переводит в одноэтажную заключительную конфигурацию |x1.

Содержание Назад Вперед