[6Typos]

Why are you using DCGs for turing_//2? Genuine question, because I implemented a TM interpreter in Prolog, using "normal" predicates, and I can't see where they help you in this case

PS: I learnt how to use DCGs thanks to your website, thank you!

[triska]

That's a justified question! I'm using DCG (semicontext) notation here analogously to monads, mostly to benefit from having to keep track of fewer explicit arguments that need to be passed around.

In this concrete case, using them explicitly is certainly not bad and may even be preferable. However, suppose I now introduce a new argument in order to implement iterative deepening:

    turing(Ls, Name, Tape0, Rs) :-
            phrase(turing_(Ls, s(q0), Name), [[]-Tape0], [_-Rs]).

    turing_([], final, _) --> [].
    turing_([_|Is], s(Q0), Name) -->
            state(Ls0-Rs0, Ls-Rs),
            { right_symbol_rest(Rs0, Symbol0, RsRest),
              tm(Name, Q0, Symbol0, Q, Symbol, Action),
              action(Action, Ls0, Ls, [Symbol|RsRest], Rs) },
            turing_(Is, Q, Name).

Then this notation, in my opinion, already makes it a bit easier to think about the rule, since it only uses 3 arguments instead of 5 or more, and the tape is simply passed along implicitly.

An iterative deepening version of the machine provides the important benefit that infinite branches of the computation cannot block others that lead to (nondeterministic) succcess. For example, suppose I add the indefinitely looping machine:

   tm(loop, q0, 1, s(q0), 1, right).
   tm(loop, q0, b, s(q0), b, right).

and then define:

    tm(loop_or_plus1_or_id, Q0, S0, Q, S, A) :- tm(loop,  Q0, S0, Q, S, A).
    tm(loop_or_plus1_or_id, Q0, S0, Q, S, A) :- tm(plus1, Q0, S0, Q, S, A).
    tm(loop_or_plus1_or_id, Q0, S0, Q, S, A) :- tm(id,    Q0, S0, Q, S, A).

then we now get solutions via iterative deepening, whereas the original machine loops without reporting any solution:

   ?- length(Is, _),
      turing(Is, loop_or_plus1_or_id, [1,1,1], Ts).
   Is = [_3790],
   Ts = [1, 1, 1] ;
   Is = [_3790, _3796],
   Ts = [1, 1] ;
   Is = [_3790, _3796],
   Ts = [1, 1] .

Iterative deepening is an asymptotically optimal search strategy under very general assumptions. Thank you for the kind words!