A nondeterministic Turing Machine simulator in C
Thank you for sharing!<p>For comparison, here is an interpreter for non-deterministic Turing machines, written in the logic programming language Prolog:<p><pre><code>    turing(Name, Tape0, Rs) :-
            phrase(turing_(s(q0), Name), [[]-Tape0], [_-Rs]).

    state(S0, S), [S] --&gt; [S0].

    turing_(final, _) --&gt; [].
    turing_(s(Q0), Name) --&gt;
            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).
</code></pre>
I have adopted the convention that <i>q0</i> is the starting state, and <i>final</i> is the final state.<p>For example, here is a (deterministic) TM that computes <i>N+1</i>, for a natural number <i>N</i> specified in unary encoding:<p><pre><code>    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).
</code></pre>
Sample query and answer:<p><pre><code>   ?- turing(plus1, [1,1,1], Ts).
   Ts = [1, 1, 1, 1] ;
   false.
</code></pre>
And here is a deterministic machine that computes the identity function id(<i>X</i>) for any natural number <i>X</i>:<p><pre><code>    tm(id, q0, 1, final, 1, stay).
    tm(id, q0, b, final, b, stay).
</code></pre>
Combining the two machines, here is a machine that <i>non-deterministically</i> computes N+1 <i>or</i> the identity function at each step of the computation where the state is q0:<p><pre><code>    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).
</code></pre>
Sample query and answer:<p><pre><code>   ?- 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.
</code></pre>
Note that alternative solutions are reported on backtracking.