/*                                     
Turing Machine in Prolog.
Copyright (C) 2017 Markus Triska (triska@metalevel.at)
Tested with Scryer Prolog.
This example demonstrates one way to describe the workings of a
Turing machine, using a logic programming language like Prolog.
The idea is to express the whole process as a relation between
*states*. In our case, the state of interest is comprised of:
) the contents of the tape
) the position of the tape head.
Given this state, we can look up what to do next, using a table of
state transitions that encodes the rules of the Turing machine.
In the following, the tape is encoded as 2 lists: One, called Ls,
describes the tape contents to the _left_ of the tape head. The
other, called Rs, describes the tape contents to the _right_ of the
tape head. In addition, Ls is encoded "in reverse", and the first
element of Rs holds the symbol under the tape head.
For example, if the tape is:
a b c d e f
===========
A

+ tape head
then we represent it as:
Ls = [c,b,a]
Rs = [d,e,f]
The tape extends indefinitely to the right and to the left. Unless
otherwise specified, each cell is blank, represented by the atom b.
We start with Ls0 = [] and Rs0 = Tape0, which is the initial tape.
If the machine reaches the final state called 'final', then we
obtain Ls and Rs, which combined represent the result of the
computation as the tape content after the computation.
Any state S that is _not_ the final state is represented as s(S),
using the symbolic wrapper s/1 that lets us cleanly distinguish the
final state from any other state, and hence keep the code pure.
We are using Prolog DCG notation to _implicitly_ thread through the
current state of the tape, and relate every state to the state
after the current step. For more information, see the DCG primer:
https://www.metalevel.at/prolog/dcg
===================================
You can supply your own definitions of tm/6 to represent any
Turing machine:
tm(+Name, +Q0, +Symbol0, Q, Symbol, Action)
The predicate is called with the following input arguments:
* Name is the the name of the Turing machine that is
currently running
* Q0 is the machine's current state
* Symbol0 is the symbol under the tape head
The predicate relates these arguments to:
* Q, the next state of the machine
* Symbol, the symbol that is written at the current position
* Action, which is either left, right, or stay, to indicate
how to move the tape head.
The main interface predicate is turing(+Name, +Tape0, Tape).
The initial state is called q0.
This program shows that Prolog is a Turing complete language.
                                     */
: use_module(library(dcgs)).
: use_module(library(lists)).
turing(Name, Tape0, Tape) :
phrase(turing_(s(q0), Name), [[]Tape0], [LsRs]),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
state(S0, S), [S] > [S0].
turing_(final, _) > [].
turing_(s(Q0), Name) >
state(Ls0Rs0, LsRs),
{ right_symbol_rest(Rs0, Symbol0, RsRest),
tm(Name, Q0, Symbol0, Q, Symbol, Action),
action(Action, Ls0, Ls, [SymbolRsRest], Rs) },
turing_(Q, Name).
action(left, Ls0, Ls, Rs0, Rs) : left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [SymbolLs0], [SymbolRs], Rs).
left([], [], Rs, [bRs]).
left([LLs], Ls, Rs, [LRs]).
right_symbol_rest([], b, []).
right_symbol_rest([SymbolRest], Symbol, Rest).
/*                                     
Example 1: TM computing (x + 1) of a number x in unary encoding.
Sample query:
? turing(plus1, [1,1,1], Ts).
%@ Ts = [1,1,1,1]
%@ ; false.
                                     */
tm(plus1, q0, 1, s(q0), 1, right).
tm(plus1, q0, b, final, 1, stay).
/*                                     
Example 2: TM producing 501 "1"s and then halting.
This machine is a Beavy Beaver candidate with 5 states (where
the final state is not counted).
Sample interaction:
? use_module(library(reif)). % for tfilter/3
%@ true.
? turing(bb5, [], Ts), tfilter(=(1), Ts, Ones), length(Ones, L).
%@ L = 501, Ones = [1,1,1,1,...], Ts = [1,1,b,1,1,1,b,1,1,1,b,...]
%@ ; false.
                                     */
tm(bb5, q0, b, s(1), 1, right).
tm(bb5, q0, 1, s(2), b, left).
tm(bb5, 1, b, s(2), 1, right).
tm(bb5, 1, 1, s(3), 1, right).
tm(bb5, 2, b, s(q0), 1, left).
tm(bb5, 2, 1, s(1), b, right).
tm(bb5, 3, b, s(4), b, right).
tm(bb5, 3, 1, final, 1, right).
tm(bb5, 4, b, s(2), 1, left).
tm(bb5, 4, 1, s(q0), 1, right).