Turing Machine in Cool

busybeaver3.in

3
1
1
1
1
2
-1
1
0
-1
1
1
1
1
1
-1
1
-1
1

busybeaver4.in

4
1
1
1
1
1
-1
1
0
-1
0
2
-1
1
-1
1
1
3
-1
1
3
1
0
0
1

busybeaver5.in

5
1
1
1
1
2
-1
1
2
1
1
1
1
1
3
1
0
4
-1
1
0
-1
1
3
-1
1
-1
1
0
0
-1

busybeaver5weak.in

5
1
1
1
0
2
-1
1
2
1
1
3
1
1
0
-1
0
1
1
0
4
1
1
-1
1
1
2
-1
1
0
1

negate.in

24 ; Number of states
0 ; 0 - Beginning - transition to input insertion.
10
0
1  ; Same.
10
0
0 ; 1 - End of input. Start adding one.
3
-1
1 ; Keep going, flipping bits.
2
1
1 ; 2 - Flip bit. Was 0, now 1.
1
1
0 ; Flip bit. Was 1, now 0.
1
1
1 ; 3 - Adding one. Got to our first zero, so now just keep bits the same.
6
-1
0 ; Adding one. Another 1, so keep adding bits this way.
4
-1
0 ; 4 - End of input. We are done.
-1
1
1 ; Not end of input. Keep going.
3
-1
0 ; 5 - Adding one but hit first zero, so keep the same.
6
-1
1 ; Adding one, but keep the same.
6
-1
0 ; 6 - End of input. We are done.
-1
1
1 ; Not end of input. Keep going.
5
-1
0 ; 7 - After putting in input, keep going back to the beginning.
9
1
1
8
-1
0 ; 8
7
-1
1
7
-1
0 ; 9
1 
1
1
1
1
1 ; 10 - Beginning of actual input. 1010100
11
1
1
11
1
1 ; 1 (input bit)
12
1
1
12
1
1 ; data signifier bit
13
1
1
13
1
0 ; 0 (input bit)
14
1
0
14
1
1 ; data signifier bit
15
1
1
15
1
1 ; 1 (input bit)
16
1
1
16
1
1 ; data signifier bit
17
1
1
17
1
0 ; 0 (input bit)
18
1
0
18
1
1 ; data signifier bit
19
1
1
19
1
1 ; 1 (input bit)
20
1
1
20
1
1 ; data signifier bit
21
1
1
21
1
0 ; 0 (input bit)
22
1
1
22
1
1 ; data signifier bit
23
1
1
23
1
0 ; 0 (input bit)
8
0
0
8
0

turing.cl

(*
 * In an attempt to show that Cool is Turing complete, I have created a
 * Turing machine simulator. This simulates a Turing machine with only
 * two characters in its alphabet (0,1) where 0 is the blank state, a 
 * dedicated start state of 0, and only one accept state (-1 or Halt).
 * It lets the user choose any  number of non-halt state (up to 2^31-1
 * --so not *quite* every Turing machine), and it lets the user chose
 * the transition function from each state and tape value to any
 * tape-value, state, and left/right/neutral head motion.
 *)

(* Basic class representing a single cell in the tape. There is a value
 * given for the current state as well as pointers to the next and previous
 * items in the tape.
 *)
class TapeCell {
    -- Position (cell number) in the tape. This is helpful for printing.
    pos : Int; 

     -- Current thing written on the tape.
    val : Bool;

    -- Pointers to the next and previous items on the tape.
    left : TapeCell;
    right : TapeCell;

    -- Accessor and modifier for pos.
    getPos() : Int {
        pos
    };

    setPos(p : Int) : SELF_TYPE {
        {
            pos <- p;
            self;
        }
    };

    -- Accessor and modifier for value.
    getVal() : Bool {
        val
    };

    setVal(b : Bool) : SELF_TYPE {
        {
            val <- b;
            self;
        }
    };

    -- Accesors and modifiers for left and right.
    getLeft() : TapeCell {
        left
    };

    setLeft(l : TapeCell) : SELF_TYPE {
        {
            left <- l;
            self;
        }
    };

    getRight() : TapeCell {
        right
    };

    setRight(r : TapeCell) : SELF_TYPE {
        {
            right <- r;
            self;
        }
    };

    -- Functions to return the cell to the left or right along the
    -- tape. If the tape is "over" (i.e., we haven't visited
    -- the next cell over), a new one gets created.
    moveLeft() : TapeCell {
        if isvoid left then {
            left <- new TapeCell;
            left.setPos(pos - 1);
            left.setRight(self);
            left;
        } else 
            left
        fi
    };

    moveRight() : TapeCell {
        if isvoid right then {
            right <- new TapeCell;
            right.setPos(pos + 1);
            right.setLeft(self);
            right;
        } else
            right
        fi
    };

    -- Methods for printing the whole tape. The strategy is
    -- to go back to the beginning of the tape using "recursion"
    -- and then to go forward. This lets us keep a pointer to
    -- an arbitrary part in the tape and still print out every
    -- visited cell.
    printFromBeginning(io : IO) : IO {
        (*
            -- Recursive statement.
            if isvoid left then
                -- Base case: print from here.
                printFromHere(io)
            else
                -- Recursive case: print from the beginning on the
                -- left
                left.printFromBeginning(io)
            fi
        *)

        -- Iterative statement.
        let cell : TapeCell <- self in {
            -- Keep going left while we can.
            while not isvoid cell.getLeft() loop cell <- cell.getLeft() pool;

            -- Keep printing cell information while we can.
            while not isvoid cell loop {
                io.out_int(cell.getPos())
                  .out_string(": ")
                  .out_string(if cell.getVal() then "1\n" else "0\n" fi);

                cell <- cell.getRight();
            } pool;

            io;
        }
    };

    printFromHere(io : IO) : IO {
        {
            -- Print out the contents of the current cell.
            io.out_int(pos)
              .out_string(": ")
              .out_string(if val then "1\n" else "0\n" fi);

            -- Continue printint out the tape if we aren't
            -- at the end of the tape.
            if not isvoid right then
                right.printFromHere(io)
            else
                io
            fi;
        }
    };

};

(* This simple class specifies a single action for the Turing machine
 * to do. The action specifies three things to do: the action to write
 * on the tape, the state to move to, and whether the tape should move
 * towards the left, towards the right, or stay where it is.
 *)
class Action {
    write : Bool; -- Value to write onto the tape.
    nstate : Int; -- New state to transition into
    movement : Int; -- Head-movement specifier -- either -1 (left), 0 (stasis), or 1 (right).

    -- Accessor and modifier for write.
    getWrite() : Bool {
        write
    };

    setWrite(w : Bool) : SELF_TYPE {
        {
            write <- w;
            self;
        }
    };

    -- Accessor and modifier for nstate.
    getNState() : Int {
        nstate
    };

    setNState(s : Int) : SELF_TYPE {
        {
            nstate <- s;
            self;
        }
    };

    -- Accessor and modifier for movement.
    getMovement() : Int {
        movement
    };

    setMovement(m : Int) : SELF_TYPE {
        {
            movement <- m;
            self;
        }
    };
};

-- The ActionTable specifies what happens given the current
-- state of the Turing machine and read value.
class ActionTable {
    action0 : Action;
    action1 : Action;
    next : ActionTable;

    -- Gets the action with the current state and the
    -- curent value.
    lookupAction(state : Int, val : Bool) : Action {
        (*
            -- Recursive statement.
            if state = 0 then
                if val then
                    action1
                else
                    action0
                fi
            else
                next.lookupAction(state - 1, val)
            fi
        *)

        -- Iterative statement. Keep going down the table until
        -- we reach the point that i = 0 (that is, retrieve the
        -- at entry i spaces down) and return its matching value.
        let at : ActionTable <- self, i : Int <- state in {
            while not i = 0 loop {
                at <- at.getNext();
                i <- i - 1;
            } pool;

            at.getAction(val);
        }
    };

    -- Accessor and modifier for next.
    getNext() : ActionTable {
        next
    };

    setNext(n : ActionTable) : SELF_TYPE {
        {
            next <- n;
            self;
        }
    };

    -- Accessor and modifier for the two actions. The action
    -- to update is specified by the Boolean "value" (which
    -- should be read).
    setAction(action : Action, val : Bool) : SELF_TYPE {
        {
            if val then
                action1 <- action
            else
                action0 <- action
            fi;
            self;
        }
    };

    getAction(val : Bool) : Action {
        if val then
            action1
        else
            action0
        fi
    };
};

(*
 * The head of the Turing machine. This has a notion of where
 * in the tape it is and also what its current state is.
 *)
class Head inherits IO {
    pos : TapeCell <- new TapeCell; -- Our current cell on the tape.
    table : ActionTable; -- The lookup table for transitions.
    state : Int <- 0; -- Start in state 0.

    -- Computation mechanism of the machine. It returns "true"
    -- if we are not in the halt state and "false" when/if we
    -- halt. (I wonder if there's some way to know if this
    -- will happen...)
    computeNext(step : Int) : Bool {
        let action : Action <- table.lookupAction(state, pos.getVal()) in {
            -- Give a feel for where we are in the computation.
            out_string("Step ").out_int(step).out_string(":\n");
            out_string("\tPosition ").out_int(pos.getPos()).out_string("\n");
            out_string("\tValue ").out_string(if pos.getVal() then "1\n" else "0\n" fi);
            out_string("\tAction state ").out_int(action.getNState()).out_string("\n");
            out_string("\tAction val ").out_string(if action.getWrite() then "1\n" else "0\n" fi);
            out_string("\tAction move ").out_int(action.getMovement()).out_string("\n");


            pos.setVal(action.getWrite());
            state <- action.getNState();


            -- Move the head based on movement.
            if action.getMovement() < 0 then
                -- Move the head to the left.
                pos <- pos.moveLeft()
            else if 0 < action.getMovement() then
                -- Move the head to right right.
                pos <- pos.moveRight()
            else
                -- Keep the head where it is.
                pos <- pos
            fi fi;

            -- Return value: If state = -1, we are done (in halt state).
            not state = ~1;
        }
    };

    -- Accessor and modifier for the action table.
    getTable() : ActionTable {
        table
    };

    setTable(t : ActionTable) : SELF_TYPE {
        {
            table <- t;
            self;
        }
    };

    -- Accessor and modifier for the tape position.
    getPos() : TapeCell {
        pos
    };

    setPos(p : TapeCell) : SELF_TYPE {
        {
            pos <- p;
            self;
        }
    };
};

(*
 * The main class reads in user input and construcs the action table. It then
 * runs the Turing machine and prints out the tape if we halt.
 *)
class Main {
    io : IO <- new IO;

    main() : SELF_TYPE {
        {
            let states : Int, table : ActionTable, tail : ActionTable, head : Head <- new Head in { 
                -- Read in the number of states from user input.
                io.out_string("How many states (not counting halt state)? ");
                states <- io.in_int();

                if states <= 0 then {
                    io.out_string("Must have at least one non-terminal state.\n");
                    abort();
                } else self fi;

                let i : Int in
                    while i < states loop {
                        io.out_string("State ")
                          .out_int(i)
                          .out_string(":\n");

                        let action0 : Action <- new Action, action1 : Action <- new Action, j : Int <- 0 in {
                            -- Read in a single action (what to do based on state, etc.
                            while j < 2 loop {
                                let wval : Int, nstate : Int, movement : Int in { 
                                    io.out_string("\tTransition for val = ")
                                      .out_int(j)
                                      .out_string(":\n");
                                    io.out_string("\t\tWrite val: ");

                                    wval <- io.in_int();

                                    if not wval = 0 then
                                        if not wval = 1 then {
                                            io.out_string("Invalid write value ")
                                              .out_int(wval)
                                              .out_string("! Please enter 0 or 1.\n");
                                            abort();
                                        } else self fi
                                    else self fi;

                                    io.out_string("\t\tNew state (-1 for halt): ");

                                    nstate <- io.in_int();

                                    if not ~1 <= nstate then {
                                        io.out_string("Invalid state ")
                                          .out_int(nstate)
                                          .out_string("! Please ever a value greater than or equal to -1 and less than the number of states.\n");
                                        abort();
                                    } else if not nstate < states then {
                                        io.out_string("Invalid state ")
                                          .out_int(nstate)
                                          .out_string("! Please ever a value greater than or equal to -1 and less than the number of states.\n");
                                        abort();
                                    } else self fi fi;

                                    io.out_string("\t\tTape movement (-1 for left, 0 for none, 1 for right): ");

                                    movement <- io.in_int();

                                    if not movement = ~1 then
                                        if not movement = 0 then
                                            if not movement = 1 then {
                                                io.out_string("Invalid movement ")
                                                  .out_int(movement)
                                                  .out_string("! Please enter either -1, 0, or 1.\n");
                                                abort();
                                             } else self fi
                                         else self fi
                                    else self fi;

                                    -- Set the appropriate action based on this information from the user.
                                    let action : Action <- if j = 0 then action0 else action1 fi in {
                                        action.setWrite(wval = 1);
                                        action.setNState(nstate);
                                        action.setMovement(movement);
                                    };
                                };
                                
                                j <- j+1;
                            } pool;

                            -- Add those two actions as the head of the action table.
                            let atTail : ActionTable <- new ActionTable in {
                                atTail.setAction(action0, false);
                                atTail.setAction(action1, true);

                                if isvoid table then {
                                    table <- atTail;
                                    tail <- atTail;
                                } else {
                                    tail.setNext(atTail);
                                    tail <- atTail;
                                } fi;
                            };

                        };

                        i <- i+1;
                    } pool;

                -- Run the simulation.
                io.out_string("Running computation...\n");
                head.setTable(table);
                let i : Int <- 0 in while head.computeNext(i) loop i <- i+1 pool;

                -- Print out the tape.
                io.out_string("End tape:\n");
                head.getPos().printFromBeginning(io);
            };
            self;
        }
    };
};