透明思考

C'mon, It's Turing Machine! (Part 2)

October 17th, 2011

(Following the 1st part )

Write Your Own Machine

File machines/an_irrational_number.machine includes all the fundamental elements to create your own Turing Machine.

The lines start with semicolons are comments.
Non-comment non-empty lines are m-configurations, each of them consists of 4 columns (separated by vertical lines), which in turn are:
- Name of current m-configuration.
- The symbol read from current square of the tape—m-configurations with same name could behave differently while reading different symbols.
- Operations, separated by commas. Valid operations are:
  - P{x}: Write {x} to current square of the tape.
  - E: Erase any symbol in current square.
  - L/R: move the cursor one square left/right.
- Next m-configuration—what should be done after current m-configuration?

Now, try to write your own machine, and run it!

What’s Next?

Universal Turing Machine , of course. (What else otherwise?)

(It requires reading Chapter 7 and 9 of The Annotated Turing . Although I haven’t started yet, I can feel it’s not an easy task. Any contribution would be highly appreciated.)

Meanwhile, I started building a web UI running Turing Machines with Compojure . Take a look at web folder. You can trial it with:

$ lein ring server

It also makes sense to tidy it up and make it more interactive.

I also want to build an iOS application…but that’s another story.

You might want to try something more interesting, e.g. to write a general Turing Machine to determine any given Turing Machine would halt or not; to solve the Entscheidungsproblem ; etc.

Anyway, enjoy :D

Posted by gigix Filed in

0 comments »

C'mon, It's Turing Machine! (Part 1)

October 12th, 2011

Spent about 10 hours, I wrote my first program with Clojure : an implementation of Turing Machine as described in Alan Turing’s famous paper ” On Computable Numbers, With An Application To The Entscheidungsproblem ”.

(Note: Charles Petzold’s book The Annotated Turing is 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 install Leiningen—which is 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 see turing_machine-1.0.0-SNAPSHOT-standalone.jar being 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 Turing Machine which calculates 1/3 and prints the result to a tape—actually we only calculate and display the starting 10 squares of the tape, because it’s simply impossible to finish the calculation, because it’s infinite.

Calculate An Irrational Number

There’s another machine lays in machines/an_irrational_number.machine, which calculates an irrational number with following form:

0.01011011101111011111…

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

$ java -jar turing_machine-1.0.0-SNAPSHOT-standalone.jar machines/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 more detail in next section: