(Followingthe 1stpart)

Write Your Own Machine

Filemachines/an_irrational_number.machineincludes 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 (separatedby verticallines), which in turn are:
  • Name of current m-configuration.
  • The symbol read from current square of the tape—m-configurations with same namecould behavedifferently 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 ofThe Annotated Turing. Although I haven’t started yet, I can feel it’s not an easy task. Any contributionwould be highlyappreciated.)

Meanwhile, I started building a web UI running Turing Machines withCompojure. Take a look atwebfolder. 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 determineany givenTuring Machine would halt or not; to solve theEntscheidungsproblem; etc.

Anyway, enjoy :D