HN Explorer

6 comments

[ 9.9 ms ] story [ 14.9 ms ] thread
[dead] stendinator
Programmed non-determinism? Yeeeeaaahhh... No.
[deleted]
(comment deleted)
sboschk
If I may add some context: this was a mandatory project for a course (Algorithms and Principles of Infomation Technology, CS&Eng BSc II year) held last year at Politecnico di Milano
triska
Thank you for sharing!

For comparison, here is an interpreter for non-deterministic Turing machines, written in the logic programming language Prolog:

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

    state(S0, S), [S] --> [S0].

    turing_(final, _) --> [].
    turing_(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_(Q, Name).

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

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

    right_symbol_rest([], b, []).
    right_symbol_rest([Symbol|Rest], Symbol, Rest).
I have adopted the convention that q0 is the starting state, and final is the final state.

For example, here is a (deterministic) TM that computes N+1, for a natural number N specified in unary encoding:

    tm(plus1, q0, 1, s(q0), 1, right).
    tm(plus1, q0, b, s(q1), 1, stay).
    tm(plus1, q1, 1, s(q1), 1, left).
    tm(plus1, q1, b, final, b, right).
Sample query and answer:

   ?- turing(plus1, [1,1,1], Ts).
   Ts = [1, 1, 1, 1] ;
   false.
And here is a deterministic machine that computes the identity function id(X) for any natural number X:

    tm(id, q0, 1, final, 1, stay).
    tm(id, q0, b, final, b, stay).
Combining the two machines, here is a machine that non-deterministically computes N+1 or the identity function at each step of the computation where the state is q0:

    tm(plus1_or_id, Q0, S0, Q, S, A) :- tm(plus1, Q0, S0, Q, S, A).
    tm(plus1_or_id, Q0, S0, Q, S, A) :- tm(id,    Q0, S0, Q, S, A).
Sample query and answer:

   ?- turing(plus1_or_id, [1,1,1], Ts).
   Ts = [1, 1, 1, 1] ;
   Ts = [b] ;
   Ts = [1] ;
   Ts = [1, 1] ;
   Ts = [1, 1, 1] ;
   false.
Note that alternative solutions are reported on backtracking.
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!