README.org

This project creates implements a Turing Machine using the scala type system, which are run completely by the compiler. The turing machine and initial state are encoded using the scala type system and implicit defs and implicit vals, and the final state of the Turing machine (if one can be calculated) is determined at compile time

This is probably not useful, other than being an interesting exploration of what is possible with the scala type system.

1 The Turing Machine

The turing machine we are trying to implement is a single tape turing machine. The tape is made up of cells which can be in one of three states: One, Zero, X.

The machine is always looking at one particular cell.

The machine is a finite state machine. Each state has transitions defined which describe the next state of the machine based on the current state of the machine and the current cell being looked at.

2 The Finite State Machine

There are three types of states the state machine might be in:

• Halt The program terminates when reaching this state, there is only one instance of this state
• LeftState When the machine arrives in a state which is a left state, the tape is re-positioned so that the machine is looking at a cell which is to the left of the previous current cell
• RightState When the machine arrives in a state which is a left state, the tape is re-positioned so that the machine is looking at a cell which is to the left of the previous current cell

3 Examples

3.1 AddOne

Here we describe a simple machine which can add one to a binary number.

It is assumed that the Machine starts looking at the most significant byte of a number, with the less significant digits to the right. The program should increment this binary number and terminate with the machine looking at the most significant digit.

The Machine starts in the FindEnd state. It remains in the find end state until we find the cell to the right of the least significant digit.

The machine transitions to the Adding state. During the adding state, it scans to the left, looking for a 0 or X it can replace with a 1. After which we have successfully incremented the number.

Then the machine Enters the FindBeginning state, which just scans to the left looking for and X, at which point we are one cell to the left of the most significant digit.

Then the RightOneMore state just advances the tape to the right so we are pointing at the MSD.

In this diagram, state transitions are labeled N:M which means, follow this transition if the tape is pointing at N, and replace the N with M.

    1:1    0:0
   +----+ +----+
   |    | |    |
   |    v |    v
+- ------------ -+
| FindEnd(right) |
+----------------+
        |
        | X:X
        |
        v
+-------      -+
| Adding(left) |
+-------      -+                  
 X:1 |  |     ^ 
 0:1 |  | 1:0 | 
     |  +-----+ 
     V                                
+---------------------+     
| FindBeginning(left) |
+---------------------+             
         |
         | X:X 
         |
         V                 0:0
+---------------------+    1:0       +------+ 
| RightOneMore(right) | -----------> | Halt | 
+---------------------+              +------+

3.2 AddOne implementation

The implementation of the AddOne turing machine is found in src/test/scala/add.scala

First we create state objects to represent all the states of the turing machine:

class FindEnd extends RightState
case object FindEnd extends FindEnd

class Adding extends LeftState
case object Adding extends Adding

class FindBeginning extends LeftState
case object FindBeginning extends FindBeginning

class RightOneMore extends RightState
case object RightOneMore extends RightOneMore

Then we add Transitions between all the states as implicit vals:

implicit val findEndOne = Transition[FindEnd.type, FindEnd.type, One.type, One.type](FindEnd,FindEnd,One)
implicit val findEndZero = Transition[FindEnd.type, FindEnd.type, Zero.type, Zero.type](FindEnd,FindEnd,Zero)
implicit val findEndX = Transition[FindEnd.type, Adding.type, X.type, X.type](FindEnd,Adding,X)


implicit val addingOne = Transition[Adding.type, Adding.type, One.type, Zero.type](Adding,Adding,Zero)
implicit val addingZero = Transition[Adding.type, FindBeginning.type, Zero.type, One.type](Adding,FindBeginning,One)
implicit val addingX = Transition[Adding.type, FindBeginning.type, X.type, One.type](Adding,FindBeginning,One)


implicit val fbOne = Transition[FindBeginning.type, FindBeginning.type, One.type, One.type](FindBeginning,FindBeginning,One)

implicit val fbZero = Transition[FindBeginning.type, FindBeginning.type, Zero.type, Zero.type](FindBeginning,FindBeginning,Zero)

implicit val fbX = Transition[FindBeginning.type, RightOneMore.type, X.type, X.type](FindBeginning,RightOneMore,X)

implicit val romX = Transition[RightOneMore.type, Halt.type, X.type, X.type](RightOneMore,Halt,X)
implicit val romOne = Transition[RightOneMore.type, Halt.type, One.type, One.type](RightOneMore,Halt,One)
implicit val romZero = Transition[RightOneMore.type, Halt.type, Zero.type, Zero.type](RightOneMore,Halt,Zero)

Then we create the starting tape that has the number 0b1101 in the expected starting position

val startTape = Tape( X :: TNil, One, One :: Zero :: One :: X :: X :: TNil)

We create a val named completed which is the result of running the Turing machine:

val completed = startTape.run(FindEnd)

HOWEVER! we don’t actually have to run the program. In the process of compiling this program, the scalac compiler has already figured out what the type of completed is, which is the Tape at the time that the Turing Machine halts. And since the Tape has all of the cells encoded in the type, we already know what the ending state of the Tape is.

We can verify at compile time that we get the result we are expecting:

// this is a utility to witness that a type is the type we think it
// is without influencing the compiler's type inference
def typed[T](t : => T) {}

// if this compiles, then "completed" is the type we think it is
typed[Tape[X :: TNil, One, One :: One :: Zero :: X :: X :: TNil ]]( completed)

And we verify that that our Turing machine added one to 0b1101 and got 0b1110

3.3 AddTwoNumbers

4 Credits:

I couldn’t have done this without the pioneering work that Miles Sabin has done in this area. The implementation of the heterogeneous lists that encode the tape are lifted right from his shapeless project.

5 License

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.