В алгоритме имеются две операции выбора:

1. V_a: если на ленте z=1, то выполняется операция R, иначе выполняется операция инвертирования (замена “0” на “1”);

2. V_b: если на ленте z=1, то выполняется операция L, иначе выполняется операция R; в обоих случаях символ в ячейке не изменяется.

О

Таблица 2.2

М1	0	1
q1	1 q2	R
q2	R !	L

перации V_a и V_b выполняются последовательно; после выполнения команды, соответствующей истинной ветви операции V_a, происходит переход на повторное выполнение операции V_а, а после выполнения команд ложной ветви – безусловный переход на V_b. После выполнения команд истинной ветви операции V_b происходит возврат на эту же операцию V_b, а после команд ложной ветви завершается работа алгоритма.

18

Итак, каждой операции выбора можно сопоставить свою строку в ФС:

V_a  q₁: 1 S q₂; 1 R q₁

V_b  q₂: 0 R ! ; 1 L q₂

Первая команда в строке соответствует символу “0” в текущей ячейке, вторая - символу “1”. Таким образом, ФС машины М1, реализующей функцию y=n+1, принимает следующий вид - (см. табл. 2.2).

Заметим, что допускается не проставлять в клетке ФС символы q_i, x_j, инициирующих и формирующих команду МТ, в случае их совпадения с символами, именующими клетку, а также символ S, если головка не передвигается.

19