3. Итерация машины.

Пусть M₀ - произвольная машина Тьюринга (данные на M₀ те же самые, что и в п.2). Построим машину M, которую назовем итерацией машины M₀ относительно предиката p(x). Для этого по Т₀ построим Т машины M. Таблица Т совпадает с Т₀ вне клеток, являющихся пустыми для Т₀. В тех клетках  Т₀, для которых p()=0, в Т стоит команда S (где  - номер строки, в которой находится эта клетка , а - начальное состояние M₀). В клетках  таблицы Т₀, для которых p()=1, в таблице Т стоит также пустая команда.

Действительно, M является итерацией M₀, т.е. работа M эквивалентна многократной работе M₀.

4. Специальный операторный язык для записи алгоритмов.

Этот язык впервые был предложен А. А. Ляпуновым в 1953 г.

1. Исходными объектами являются операторы, которые подразделяются на три группы:

   1. Операторы, осуществляющие преобразование записи ленты, состояния машины и перемещение головки. Эти операторы обозначаются заглавными латинскими буквами;

   2. Операторы проверки логических условий, обозначаемые символами или (p-предикат);

   3. Специальные операторы, обозначаемые символами * или .

2. Из операторов по определенным правилам строятся операторные схемы. Операторная схема представляет собой некоторую последовательность операторов, в которой для всех стрелок в операторах проверки логических условий указаны операторы, к которым эти стрелки ведут. Например, выражение будет операторной схемой.

3. Операторная схема определяет следующую последовательность преобразований записи ленты, состояний машины и перемещений головки машины:

   1. В данный момент начинает работать тот оператор, перед которым стоит символ *;

   2. Пусть имеется ситуация *A. Тогда по окончании работы оператора A фрагмент схемы *A перейдет в фрагмент A*, т.е. преобразуется также и операторная схема;

   3. Пусть мы имеем * (или * ). В этом случае происходит вычисление предиката p по имеющейся записи на ленте и состоянию машины. Если p=1, то фрагмент * преобразуется в *, т.е. мы перейдем к выполнению следующего оператора; если p=0, то фрагмент * преобразуется в , т.е. выполняется далее оператор, к которому ведет стрелка. Для * - аналогичное правило, здесь p – трехзначный предикат: *  *_(1), *  ₍₂₎ , *  _{(0) ;}

4. Сочетание * обозначает конец преобразований или окончание работы.

Пример. Рассмотрим операторную схему .

Пусть операторы A₀ и A₁ обозначают преобразования записи ленты, состояний и положения головки, осуществляемые соответственно машинами M₀ и M₁. Предположим, что состояния машин M₀ и M₁ не пересекаются. Пусть p(x) – предикат, определенный на номерах ячеек ((,q)), на которых машина M₀ останавливается. Тогда операторная схема осуществляет следующее преобразование.

1. Имеем *A₀. Работает машина M₀ до останова в ячейке с номером, скажем, . Схема перейдет в .

2. Имеем *p. Вычисляется предикат p:

   1. если p=1, то получаем схему ;

   2. если p=0, то получаем схему .

3. a) Имеем *A₁. Работает машина M₁. В случае остановки машины M₁, приходим к схеме .

b) Имеем *Преобразование закончено.

Замечание. Преобразование, осуществляемое данной операторной схемой, является преобразованием, осуществляемым последовательным подключением машины M₁ к M₀ относительно предиката p(x).

Пример. Дана операторная схема , очевидно, что она характеризует преобразование, которое получается при итерации машины относительно предиката p(x). Действительно,

*A₀  : a) p=0  ;

b) p=1  .