A nondeterministic Turing Machine simulator in C(github.com)
github.com
A nondeterministic Turing Machine simulator in C
https://github.com/0novanta/nondeterministic-turing-machine-simulator
6 comments
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!
PS: I learnt how to use DCGs thanks to your website, thank you!
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:
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:
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).
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).
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).
?- 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] .
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
[deleted]
For comparison, here is an interpreter for non-deterministic Turing machines, written in the logic programming language Prolog:
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:
Sample query and answer:
And here is a deterministic machine that computes the identity function id(X) for any natural number X:
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:
Sample query and answer:
Note that alternative solutions are reported on backtracking.