Please explain this Turing Machine simulator written in Prolog

Question

The Wikipedia Prolog article includes this Turing Machine simulator:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

It gives a sample program that:

• On reading a "1", moves the head right.
• On reading a blank, writes a one and enters the final state.

Program:

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

The program is run as shown:

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

I understand the meaning of some of the variable names in rules/facts:

turing(Tape0, Tape)

• tape0 is the input tape
• tape is the output tape

rule(Q0, Sym, Q1, NewSym, Action)

• Q0: start state
• Sym: symbol read
• Q1: end state
• NewSym: symbol to write
• Action: how to move the head

I do not understand the meanings of the variables in these rules/facts:

perform(Q0, Ls0, Ls, Rs0, Rs)

symbol([Sym|Rs], Sym, Rs)

action(left/stay/right, Ls0, Ls, Rs0, Rs)

left([L|Ls], Ls, Rs, [L|Rs])

Can anyone explain?

Answer 1

In the Turing machine, at any given state, the write head is pointing at a particular place on the tape. There will be symbols left of the head, and symbols right of the head.

Looking at the first, main predicate:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).

It's going to "run the machine" by calling perform/5. The arguments for perform(Q0, Ls0, Ls, Rs0, Rs) represent:

Q0 - the current state (or initial state before the "perform")
Ls0 - the current set of symbols that are LEFT of the head
Ls - the FINAL set of symbols that WILL BE left of the head after perform
Rs0 - the current set of symbols that are RIGHT of the head
Rs - the FINAL set of symbols that WILL BE right of the head after perform

Initially, there are no symbols left of the head. Tape0 initially contains all the symbols to the right of the head. To "run the machine", the main predicate calls:

perform(Q0, [], Ls, Tape0, Rs)

It starts with the initial state, Q0, has no symbols left of the head to start with ([]) and has the symbols in Tape0 right of the head to start. It is expecting, upon completion of the query, to have Ls instantiated with the final set of symbols left of the head, and Rs the final set of symbols right of the head.

Everything else now supports perform/5.

symbol([Sym|Rs], Sym, Rs)

This defines a relation between the list of symbols [Sym|Rs], and the first symbol in that list (Sym) and the rest of the list (Rs). perform/5 uses this predicate to read the next symbol which is currently to the right of the head.

For this to work correctly in the context it is used, the perform/5 predicate maintains the Rs0 variable such that it is correctly in order where the head of the list is the first symbol on the right, the second element of the list is the following symbol on the right, and so on. Note that this is not the case of the list of symbols on the left. The left side list is maintained in reverse order of how the symbols appear on the tape. The reason is so that they can be considered in order of how far left they are of the current head position. More on this a little later.

action(left/stay/right, Ls0, Ls, Rs0, Rs)

This is where the action is. :) Its role is to perform the given action and provide the correctly updated lists of what's left and right of the new head position after that one action is taken. Ls0 and Rs0 are the lists of symbols left and right of the head, respectively, before the action is performed. And Ls and Rs are the symbols left and right of the head, respectively, after the action is performed.

action(stay, Ls, Ls, Rs, Rs).

This action says that when I stay, the symbols to the left and to the right of the head don't change.

action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

This action says that when I move the head right one symbol position, the symbol immediately to the right (which is Sym since the right set of symbols is [Sym|Rs]) becomes the symbol immediately to the left. The left set of symbols was originally, Ls0 and becomes [Sym|Ls0]. The list of symbols to the right was originally [Sym|Rs] and becomes Rs.

The left action gets a little more complicated than stay or right because when there are no more symbols on the left and a move left is indicated, the head still moves left and a blank appears on the right. So left it's broken out into a separate, small predicate:

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).

left([], [], Rs0, [b|Rs0]).

Here, if the left set of symbols is empty ([]) then moving left means the left symbols remains empty ([]) and a new blank (b) appears on the right of the head, at the head of the original set of right symbols (the right-hand list changes from Rs0 to [b|Rs0]).

left([L|Ls], Ls, Rs, [L|Rs]).

Here there are some symbols on the left and the action is to move left. The initial set of symbols to the left is [L|Ls] (L is the symbol immediately to the left of the head) and the initial set of symbols to the right of the head are Rs. When the head moves left, then the first symbol on the left becomes the first symbol on the right. So the updated left set of symbols is Ls, and the updated right set of symbols is [L|Rs].

The action(left, ...) predicate could have been written without the auxiliary predicate, left/4, this way:

action(left, [], [], Rs0, [b|Rs0]).
action(left, [L|Ls], Ls, Rs, [L|Rs]).

Back to the left list and the original turing/2 predicate: after turing/2 calls perform(q0, [], Ls, Tape0, Rs), it has a final set of symbols on the right (Rs) which are in the correct order, left-to-right. However, the final set of symbols on the left (Ls) are listed right-to-left (since their in order of how close they are to the current head position). Therefore, in order to show the entire tape in proper order, the left list of symbols has to be reversed, and then prepended to the right set of symbols. Thus, the calls:

reverse(Ls, Ls1),
append(Ls1, Rs, Tape).

Breaking down the perform/5 predicate:

perform(qf, Ls, Ls, Rs, Rs) :- !.

This says that if we're at the final state qf, then the final list of left symbols, Ls, becomes our current set of left symbols. Similarly for the right symbols.

perform(Q0, Ls0, Ls, Rs0, Rs) :-
    % Read the symbol to the right of the head (Sym)
    %
    symbol(Rs0, Sym, RsRest),

    % Apply first found matching rule to the current state (Q0)
    %   and the current symbol on the right (Sym), resulting in
    %   a new symbol (NewSym) and an action (Action)
    %
    once(rule(Q0, Sym, Q1, NewSym, Action)),

    % Perform the action using the current list of symbols on the left (Ls0)
    %  and the updates list of symbols on the right (old right symbol (Sym)
    %  replaced by the new right symbol (NewSym), which is [NewSym|RsRest]
    %  with the action resulting in new left Ls1 and new right Ls2
    %  sets of symbols
    %
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),

    % Recursively perform the Turing engine on the new state, left,
    %  and right sets of symbols until we hit the final state (qf)
    %  with final result being left symbols, Ls, and right symbols, Rs
    %
    perform(Q1, Ls1, Ls, Rs1, Rs).