Spent about 10 hours, I wrote my first program withClojure: an implementation ofTuring Machineas described in Alan Turing’s famous paper ”On ComputableNumbers, With AnApplication To The Entscheidungsproblem”.

(Note: Charles Petzold’s bookThe Annotated Turingis a good point to understand Turing’s paper.)

Get Started

First of all, you need clone the codebase from GitHub:

$ git clone git://github.com/gigix/turing_machine.git

In order to build it, you also need installLeiningen—whichis pretty easy on my MacBook Pro with MacPorts:

$ sudo port install leiningen

Now you can build the codebase and see if everything works:

$ cd turing_machine/clojure && ./build.sh

You should seeturing_machine-1.0.0-SNAPSHOT-standalone.jarbeing packaged, as well as a “tape” being printed as following:

(0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1)

That’s the binary form of rational number 1/3 (0.010101…). You just executed a TuringMachine whichcalculates 1/3 and prints the result to a tape—actually we only calculate and display thestarting 10squares of the tape, because it’s simply impossible to finish the calculation, because it’sinfinite.

Calculate An Irrational Number

There’s another machine lays inmachines/an_irrational_number.machine, whichcalculates anirrational number with following form:

0.01011011101111011111…

You can run this machine with following instruction—the algorithm is more complicated, so youhave to runmore steps to see a reasonable shape:

$ java -jar turing_machine-1.0.0-SNAPSHOT-standalone.jarmachines/an_irrational_number.machine 1000

The starting part of the tape looks like following:

And here’s the “source code” (formal name should be “m-configurations”,in which“m” stands for “machine”) of this machine, which I will explain in moredetail in nextsection:

(To be continued…)