/*
   Paul Y Gloess, http://www.enseirb.fr/~gloess/
     Created on   14 April 2009,
     Last edition 26 April 2009.

   Purpose:
   -------

    Template file for turing.pl,
      Turing machine.

    Note: Upon completing this template, replacing
           the ??? occurrences, save the file as
           turing.pl, so that you can run the
           query examples.

*/

/*

   A Xerox machine example
   -----------------------

      IState:    init, ITape: #####abcb#
                                  ^
      OState: allDone, OTape: bcba#****#
                                  ^
      The Turing program:

                        init: #\#, right, goto lookForLetter
               lookForLetter: #\#, left, goto allDone
                              *\*, right, goto lookForLetter
                              a\*, left, goto copyA
                              b\*, left, goto copyB
                              c\*, left, goto copyC
                       copyA: #\#, left, goto outputA
                              *\*, left, goto copyA
                     outputA: a\a, left, goto outputA
                              b\b, left, goto outputA
                              c\c, left, goto outputA
                              #\a, right, goto data
                       copyB: #\#, left, goto outputB
                              *\*, left, goto copyB
                     outputB: a\a, left, goto outputB
                              b\b, left, goto outputB
                              c\c, left, goto outputB
                              #\b, right, goto data
                       copyC: #\#, left, goto outputC
                              *\*, left, goto copyC
                     outputC: a\a, left, goto outputC
                              b\b, left, goto outputC
                              c\c, left, goto outputC
                              #\c, right, goto data
                        data: a\a, right, goto data
                              b\b, right, goto data
                              c\c, right, goto data
                              #\#, right, goto lookForLetter
                     allDone: *\*, left, goto allDone
                              #\#, halt     

*/

init(L, '#', [H | R], Tape) :-
  lookForLetter(['#' | L], H, R, Tape).

lookForLetter(???, ???, ???, Tape) :-
  allDone(???, ???, ???, Tape).
lookForLetter(???, ???, ???, Tape) :-
  lookForLetter([???, ???, ???, Tape).
lookForLetter(???, ???, ???, Tape) :-
  ???.
lookForLetter(???, ???, ???, Tape) :-
  ???.
lookForLetter(???, ???, ???, Tape) :-
  ???.

copyA(???, ???, ???, Tape) :-
  ???.
copyA(???, ???, ???, Tape) :-
  ???.

outputA(???, ???, ???, Tape) :-
  ???.
outputA(???, ???, ???, Tape) :-
  ???.
outputA(???, ???, ???, Tape) :-
  ???.
outputA(???, ???, ???, Tape) :-
  ???.

copyB(???, ???, ???, Tape) :-
  ???.
copyB(???, ???, ???, Tape) :-
  ???.

outputB(???, ???, ???, Tape) :-
  ???.
outputB(???, ???, ???, Tape) :-
  ???.
outputB(???, ???, ???, Tape) :-
  ???.
outputB(???, ???, ???, Tape) :-
  ???.

copyC(???, ???, ???, Tape) :-
  ???.
copyC(???, ???, ???, Tape) :-
  ???.

outputC(???, ???, ???, Tape) :-
  ???.
outputC(???, ???, ???, Tape) :-
  ???.
outputC(???, ???, ???, Tape) :-
  ???.
outputC(???, ???, ???, Tape) :-
  ???.

data(???, ???, ???, Tape) :-
  ???.
data(???, ???, ???, Tape) :-
  ???.
data(???, ???, ???, Tape) :-
  ???.
data(???, ???, ???, Tape) :-
  ???.

allDone([H | L], *, R, Tape) :-
  allDone(L, H, [* | R], Tape).
allDone(L, '#', R, [L, '#', R]).

/*
   Suggested query:
   ---------------

   reconsult(turing),
     init(['#', '#', '#', '#'], '#', [a, b, c, b, '#'], Tape).

   Tape = [[a, b, c, b], #, [*, *, *, *, #]] ? ;
   no (more) solutions
*/

/*
   General Turing machine
   ----------------------

*/
/*
   turing(IS, IT, OS, OT, P)
   -------------------------
      means that OS and OT are output state and tape
        after execution of Turing program P, starting
        with initial state IS and initial tape IS.
*/
turing(IState, ITape, OState, OTape, Program) :-
  instruction(IState, ITape, Program, Instruction),
  turing(IState, ITape, OState, OTape, Program, Instruction).

/*
   instruction(S, T, P, I)
   -----------------------
     means that I is the P instruction to be executed in state S
       of the machine, and state T of the tape and head.
*/
instruction(State, [_, H, _], Program, [State, H, OH, InstructionCode, OState]) :-
  member([State, H, OH, InstructionCode, OState], Program).

/*
   turing(IS, IT, OS, OT, P, I)
   ----------------------------
     means the same as turing(IS, IT, OS, OT, P) knowing
       that instruction(IS, IT, P, I) holds, in other words,
       that I is the instruction of program P corresponding
       to IS state and symbol facing the head on IT tape.
*/
turing(IState, [L, H, R], IState, [L, H, R], _,
       [IState, H, _, halt | _]).
turing(IState, [???, ???, ???], OState, OTape, Program,
       [IState, IH, OH, left, State]) :-
  turing(State, [???, ???, ???], OState, OTape, Program).
turing(IState, [[], IH, IR], OState, OTape, Program,
       [IState, IH, OH, left, State]) :-
  turing(State, [???, ???, ???], OState, OTape, Program).
turing(IState, [???, ???, ???], OState, OTape, Program,
       [IState, IH, OH, right, State]) :-
  turing(State, [???, ???, ???], OState, OTape, Program).
turing(IState, [IL, IH, []], OState, OTape, Program,
       [IState, IH, OH, right, State]) :-
  turing(State, [???, ???, ???], OState, OTape, Program).


/*

   Suggested query:
   ---------------

   reconsult(turing),
     turing(e1, [[], 1, [1, 1]], State, Tape,
            [[e1, '#', unused, halt, unused],
             [e1, 1, '#', right, e2],
             [e2, 1, 1, right, e2],
             [e2, '#', '#', right, e3],
             [e3, 1, 1, right, e3],
             [e3, '#', 1, left, e4],
             [e4, 1, 1, left, e4],
             [e4, '#', '#', left, e5],
             [e5, 1, 1, left, e5],
             [e5, '#', 1, right, e1]]).

   State = e1
   Tape = [[1, 1, 1], #, [1, 1, 1]] ? ;
   no (more) solutions
*/