! ... 0111011110110111111100 ... , Или так: ! ... 0111111100 ... ,

В первом случае сохранены исходные данные.

Пустые ячейки ленты правее исходной последовательности чисел (n₁, n₂, ... , n_m) могут быть использованы для размещения промежуточных результатов вычисления заданной функции у. Однако нужно помнить, что лента слева ограничена, поэтому возможно достижение левого конца ленты при записи информации на ленту. Программно такая ситуация не определяется, происходит аварийный останов МТ. Поэтому для записи промежуточных вычислений предпочтительнее использовать ячейки, расположенные правее заданной последовательности чисел.

2.2.2. Примеры построения машин Тьюринга

Рассмотрим примеры синтеза МТ для различных числовых функций.

Решение поставленной задачи должно быть описано в соответ-ствии с рекомендациями по данному разделу.

Пример 2.2. Постановка задачи: синтезировать МТ, вычисляющую функцию y=n+1 (операция инкремента). Сохранение исходного числа n не требуется.

Идея решения в данном случае проста: необходимо переместить головку к концу заданного числа и следующий за ним символ (а это - 0, открывающий потенциально бесконечный ряд пустых ячеек) заменить на единицу.

Словесное описание алгоритма: головка автомата движется вправо вдоль последовательности единиц, пока не встретит пустую ячейку. В эту ячейку записывается “1”, и головка движется влево вдоль единиц результата (числа у), пока не встретит пустую ячейку. Обнаружив её, головка сдвигается вправо на одну ячейку, и МТ останавливается (головка обозревает крайнюю слева единицу результата у).

Здесь же проводится анализ словесного описания алгоритма с целью определения выполняемых операций и их последовательности, а также требуемых символов на ленте.

В данном примере МТ выполняет две макрооперации - прохождение группы единиц вправо и затем прохождение группы единиц влево. Множество используемых символов: Х={0,1}; дополнительные символы не требуются.

Схема алгоритма. Введем следующие обозначения.

Для команд перемещения головки:

• R(L) - сдвинуть вправо (влево) на одну ячейку;

• GRx_i(x_j) (GLx_i(x_j)) - двигаться вправо (влево), пропуская группу сим-волов x_i  Х, пока не встретится ячейка с символом x_î  Х (после выполне-ния команды головка находится напротив ячейки, содержащей символ x_î); например, GR1(0) - двигаться вправо до пустой ячейки, пропуская группу единиц.

Для команд, оперирующих с содержимым текущей ячейки:

• z=x_i - проверка наличия символа x_î  Х в текущей ячейке;

• z x_i - записать в текущую ячейку символ x_î  Х;

• INV - замена “1”(“0”) на “0”(“1”).

Схема алгоритма операции инкремента представлена на рис 2.3.

Анализ схемы алгоритма

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

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

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

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

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

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

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

П

Таблица 2.2

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

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

В табл. 2.3 представлена работа машины М1, т. е. расписаны по тактам её конфигурации; исходное число на ленте n=2.

Таблица 2.3

Такт	Состояние	Ситуация на ленте
0	q1	. . . 0 1 1 1 0 0 . . .
1	q1	. . . 0 1 1 1 0 0 . . .
2	q1	. . . 0 1 1 1 0 0 . . .
3	q1	. . . 0 1 1 1 0 0 . . .
4	q2	. . . 0 1 1 1 1 0 . . .
5	q2	. . . 0 1 1 1 1 0 . . .
6	q2	. . . 0 1 1 1 1 0 . . .
7	q2	. . . 0 1 1 1 1 0 . . .
8	q2	. . . 0 1 1 1 1 0 . . .
9	!	. . . 0 1 1 1 1 0 . . .