Машина Тьюринга на SETL

[vak]

Продолжаю штудировать книжку про SETL. Среди примеров имеется реализация машины Тьюринга. Не без опечаток, но их оказалось несложно поправить. Вот исходный код turing-simulate.setl:

program Turing_simulate;                    $ Turing machine simulator

if (atps := read_check()) = om then
    stop;                                   $ illegal specification
end;
[action, tape, position, state] := atps;    $ unpack action table, initial
                                            $ tape, initial position, and
                                            $ initial state
print_tape(tape, position, state);
(while (act := action(tape(position), state)) /= om)
                                            $ until stop
    [tape(position), state, n] := act;      $ write new character to tape
                                            $ and change internal state
    if (position + := n) < 1 then           $ moved left to brand-new square
        tape := [' '] + tape;               $ add blank square at left
        position := 1;                      $ and adjust position pointer
    elseif position > #tape then            $ moved right to brand-new square;
        tape with := ' ';                   $ add blank at right
    end if;
    print_tape(tape, position, state);
end while;

print;
print('Simulation ended. Chapter and state are:', tape(position), state);

proc read_check;                            $ reads and checks action table,
                                            $ tape, initial position, and
                                            $ initial state
    open('TUR.IN', 'TEXT-IN');
    reada('TUR.IN', actuples, tape, position, state);
    action := {[[c, s], [c2, s2, n]] : [c, s, c2, s2, n] in actuples};

    not_single := false;

    (for im = action{cs} | #im > 1)         $ action is not single-valued
        not_single := true;
        print;
        print('action is indeterminate in condition', cs);
        print('actions could be:');
        (for [c2, s2, n] in im)
            print(c2, s2, n);
        end for;
        print;
    end for;

    if not_single then
        return om;                          $ as indication of error in action table
    end;
    if not (bad_cs := {cs: [c2, s2, n] = action(cs) | n notin {-1, 1, 0}}) = {} then
        print('Illegal tape-motion indicators occur for conditions:', bad_cs);
    end if;
    if not is_integer(position) then
        print('Illegal initial position:', position);
    end if;
    if not is_tuple(tape) then
        print('Illegal initial tape:', tape);
    end if;
    if not forall t = tape(i) | is_string(t) and #t = 1 then
        print('Illegal initial tape', tape);
    end if;

    $ now add extra blanks to the initial tape if necessary

    if position > #tape then                $ extend tape with additional
                                            $ blank squares
        tape + := (#tape - position)*[' '];
    elseif position < 1 then                $ add extra blank squares to left
        tape := (1 - position)*[' '];
        position := 1;                      $ adjust index of position on
                                            $ extended tape
    end if;
    return [action, tape, position, state];
end proc read_check;

proc print_tape(tape, position, state);     $ Turing machine tape print
                                            $ utility.

    $ This procedure is used to display the state of the Turing machine tape at
    $ the end of each cycle of simulation

    const HSQ = 9;                          $ one-eighth screen size

    topline := (HSQ*6 - 2)*'_';
    topline(3*HSQ + 1 ... 3*HSQ + 4) := 'vvvv';
    tape_string := (HSQ*' ') +/ tape + (HSQ*' ');
                                            $ convert tape to string and pad
                                            $ with blanks.
    tape_string := tape_string(position..position + 2*HSQ - 1);

    picture := +/ ['|' + t + ' ' : t in tape_string];
    picture(1) := ' ';                      $ remove first vertical bar.
    print;
    print(topline);
    print(picture + ' ' + str state);

end proc print_tape;
end program Turing_simulate;

Попробуем запустить на этой машине Тьюринга пример из википедии, который удваивает входную последовательность единиц. Программа Тьюринга состоит из четырёх элементов: действия, входная лента, позиция и состояние.

{
    [ ' ', 1, ' ', 0,  0 ],
    [ '1', 1, ' ', 2,  1 ],
    [ ' ', 2, ' ', 3,  1 ],
    [ '1', 2, '1', 2,  1 ],
    [ ' ', 3, '1', 4, -1 ],
    [ '1', 3, '1', 3,  1 ],
    [ ' ', 4, ' ', 5, -1 ],
    [ '1', 4, '1', 4, -1 ],
    [ ' ', 5, '1', 1,  1 ],
    [ '1', 5, '1', 5, -1 ]
}
['1', '1', '1']
1
1

Запускаем:

$ ./turing-simulate.setl

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |  |1 |1 |1 |  |  |  |  |  |   1

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |  |1 |1 |  |  |  |  |  |  |   2

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |1 |1 |  |  |  |  |  |  |  |   2

___________________________vvvv_____________________
   |  |  |  |  |  |  |1 |1 |  |  |  |  |  |  |  |  |   2

___________________________vvvv_____________________
   |  |  |  |  |  |1 |1 |  |  |  |  |  |  |  |  |  |   3

___________________________vvvv_____________________
   |  |  |  |  |  |  |1 |1 |  |1 |  |  |  |  |  |  |   4

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |1 |1 |  |1 |  |  |  |  |  |   5

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |  |1 |1 |  |1 |  |  |  |  |   5

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |  |  |1 |1 |  |1 |  |  |  |   5

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |1 |1 |1 |  |1 |  |  |  |  |   1

___________________________vvvv_____________________
   |  |  |  |  |  |  |1 |  |1 |  |1 |  |  |  |  |  |   2

___________________________vvvv_____________________
   |  |  |  |  |  |1 |  |1 |  |1 |  |  |  |  |  |  |   2

___________________________vvvv_____________________
   |  |  |  |  |1 |  |1 |  |1 |  |  |  |  |  |  |  |   3

___________________________vvvv_____________________
   |  |  |  |1 |  |1 |  |1 |  |  |  |  |  |  |  |  |   3

___________________________vvvv_____________________
   |  |  |  |  |1 |  |1 |  |1 |1 |  |  |  |  |  |  |   4

___________________________vvvv_____________________
   |  |  |  |  |  |1 |  |1 |  |1 |1 |  |  |  |  |  |   4

___________________________vvvv_____________________
   |  |  |  |  |  |  |1 |  |1 |  |1 |1 |  |  |  |  |   5

___________________________vvvv_____________________
   |  |  |  |  |  |  |  |1 |  |1 |  |1 |1 |  |  |  |   5

___________________________vvvv_____________________
   |  |  |  |  |  |  |1 |1 |1 |  |1 |1 |  |  |  |  |   1

___________________________vvvv_____________________
   |  |  |  |  |  |1 |1 |  |  |1 |1 |  |  |  |  |  |   2

___________________________vvvv_____________________
   |  |  |  |  |1 |1 |  |  |1 |1 |  |  |  |  |  |  |   3

___________________________vvvv_____________________
   |  |  |  |1 |1 |  |  |1 |1 |  |  |  |  |  |  |  |   3

___________________________vvvv_____________________
   |  |  |1 |1 |  |  |1 |1 |  |  |  |  |  |  |  |  |   3

___________________________vvvv_____________________
   |  |  |  |1 |1 |  |  |1 |1 |1 |  |  |  |  |  |  |   4

___________________________vvvv_____________________
   |  |  |  |  |1 |1 |  |  |1 |1 |1 |  |  |  |  |  |   4

___________________________vvvv_____________________
   |  |  |  |  |  |1 |1 |  |  |1 |1 |1 |  |  |  |  |   4

___________________________vvvv_____________________
   |  |  |  |  |  |  |1 |1 |  |  |1 |1 |1 |  |  |  |   5

___________________________vvvv_____________________
   |  |  |  |  |  |1 |1 |1 |  |1 |1 |1 |  |  |  |  |   1

___________________________vvvv_____________________
   |  |  |  |  |  |1 |1 |1 |  |1 |1 |1 |  |  |  |  |   0

Simulation ended. Chapter and state are:   0