🚀 go-pugleaf

In article <meskes.714916931@ulysses>
meskes@ulysses.informatik.rwth-aachen.de (Michael Meskes) writes:

   All the answers are quite interesting but the don't solve the
   problem.  As far as I know Prolog is turing-complete and the proofs
   I know don't use the Cut. So why isn't it possible to solve this
   problem im Prolog?

rok put his thumb on the answer... you can easily interpret languages
which implement things like if/then/else in pure prolog even if you
can't implement if/then/else directly.  in particular, the code for a
turing machine interpreter is only a few lines.  this proves turing
equivalence, and means that if you really wanted to, you could write
an interpreter for prolog _with_ a cut to run on this turing machine.
this wouldn't count as a correct answer on most exams (or homeworks!).

Just for example, here is just such a simulator (the turing machine
program is encoded in the step predicate):

turing(Tape, State, FinalTape, FinalState) :-
    step(State, Visible, NewState, NewCell, Direction),
    change_tape(NewCell, Tape, Direction, NewTape),
    turing(NewTape, NewState, FinalTape, FinalState).

turing(Tape, done, Tape, done).

change_tape(New, tape(_, [L|Left], Right), left, tape(L, Left, [New|Right])).
change_tape(New, tape(_, Left, [R|Right]), right, tape(R, [New|Left], Right)).
    
    
--

There ain't nothin' in this world that's worth being a snot over.
	Larry Wall