, перемещается на один шаг вправо (вспомним, что команда
STOP эквивалентна
R.STOP) и останавливается. Тем самым к последовательности из четырех единиц прибавляется еще одна, превращая — как и требовалось —
4 в
5.
В качестве несколько более трудного упражнения можно проверить, что машина UN х 2, определяемая набором инструкций
00 → 00R
01 → 10R
10 → 101L
11 → 11R
100 → 110R
101 → 1000R
110 → 01.STOP
111 → 111R
1000 → 1011L
1001 → 1001R
1010 → 101L
1011 → 1011L
удваивает унарное число, как и должно быть, судя по ее названию.
Чтобы понять, как работает машина EUC, нужно явным образом задать пару подходящих чисел, скажем, 6 и 8. Как и ранее, изначально машина находится во внутреннем состоянии 0 и расположена слева, а лента выглядит следующим образом:
… 0000011111101111111100000….
После того, как машина Тьюринга после большого числа шагов останавливается, мы получаем ленту с записью вида
…000011000000000000…,
при этом машина располагается справа от ненулевых цифр. Таким образом, найденный наибольший общий делитель равен 2 (как и должно быть).
Исчерпывающее объяснение, почему машина EUC (или UN х 2) на самом деле осуществляет действие, для которого она предназначена, включает в себя некоторые тонкости, и разобраться в нем, может быть, даже труднее, чем понять устройство самой машины — довольно обычная ситуация с компьютерными программами! (Чтобы полностью понять, почему алгоритмические процедуры делают то, что от них ожидается, необходима определенная интуиция. А не являются ли интуитивные прозрения сами алгоритмическими? Это один из вопросов, которые будут для нас важны в дальнейшем.) Яне буду пытаться дать здесь такое объяснение для приведенных примеров EUC или UN х 2. Читатель, шаг за шагом проверив их действие, обнаружит, что я незначительно изменил обычный алгоритм Евклида, чтобы получить более компактную запись в рамках используемой схемы. И все же описание EUC остается достаточно сложным, включая в себя 22 элементарные инструкции для 11 различных внутренних состояний. В основном эти сложности носят чисто организационный характер. Можно отметить, например, что из этих 22 инструкций только 3 в действительности изменяют запись на ленте! (Даже для UN х 2 я использовал 12 инструкций, половина из которых меняют запись на ленте.)
