By:  Tom Briggs

Alan Turing   Alan Mathison Turing, was arguably one of the most significant Computer Scientists so far.  During the early part of the 20th century, while working on computation theories, developed the concept of a "logic" machine.  In a 1936 paper, "On Computable Numbers with an Application to the Entscheidungs-Problem", he introduced Turing Machines.  These simple structures are the logical structures, from which, other more advanced structures arise.
    Turing did more than develop these logical machines, using Goedel's theorem, he proved that there are mathematically defined questions these machines cannot answer.  The importance of these very early and base theories is often ignored by today's programmers.  According to later theories, it can be shown that the problem space of Parallel Computers is the same as the problem space of Sequential computers, that is, a Cray Supercomputer can solve the same problem set as an Intel i8086.  Parallel computers can, of course, solve them much quicker.

    The Turing Machine partially implemented here was written as an excercise in Java programming.  The Java applet will accept elements of a Turing Machine, and allow that Turing Machine to run on the input.  A Turing Machine is a collection of five things.  They are: an input alphabet, an input tape, a tape head, output alphabet, and a set of rules.
    The input tape is a "virutal" tape, which is, in this implementation, infinite in only one direction.  There is a theorem that proves that an N-tape Turing Machine has the same computation power as a one-tape Turing Machine.  There also exists a theorm that proves that a Turing Machine with a tape defined to be infinite in both directions has the same computation power as a Turing Machine with an infinite tape in only one direction.
    The input alphabet (normally the same as the output alphabet), is the set of characters which can be read from the tape.  The output alphabet is the set of characters that can be read from the tape.
    The rules define the actions of the Turing Machine.  The TM rules show that, given a current state and an input from the input set, a new value can be written to the tape, the tape head moved one increment in a specified direction, and a transition made to a new state.

For example, given the following set of rules:
 

Current
State		 Input
Character		 Write
Character		 Head
Direction		 Next
State
1 a a R 1
1 b b R 1
1 blank blank R ACCEPT
 If the input tape consisted of a string of a's and b's, this simple machine would "walk" from the origin to the end of the tape until it read a blank.  This is the method which can be used to enter rules into the Java Turing Machine below.

 

Java Turing Machine
 


 
 

 

Instructions

Entering Rules
    There are two methods available for entering rules.  Method #1 is using the Add / Edit rules button.  This button will add or replace a rule in the rule table.  If you enter a rule that has the same current state and read character as an existing rule, the new rule will replace the existing rule.
    The second method is to use the Load Rule URL button.  This button will fetch a rule file from a given URL.  There are several canned rules available in the rules subdirectory (index of rule directory).  You can also specify your own rules, beware of your Applet security model.  This may restrict your attempts!
  • Rules are of the following format:
  • Lines beginning with // are comments
  • All other lines are treated as rule lines.
  • Rule lines consist of 5 elements, seperated by commas.  The elements are: current rule, read character, write character, direction, next rule.
  • Current rule is the rule number
  • Read character is the character that is visible at the tape head in that rule
  • Write character is the character that is to replace the read character on the tape
  • Direction is either R or L, and is the direction to move the tape (one cell)
  • Next rule is the next rule to follow.  rule 0 is reserved for accept states, -1 is reserved to cause a crash
Example rule:
    // read the entire tape, accept a's and b's
    1,a,a,R,1
    1,b,b,R,1
    1, , ,R,0
Rules can be extremely complicated.  In fact, to do even simple operations, 50 to 100+ rules are often required.

Input Tape
    When you enter your rules, you also need to enter your input tape.   The Input Tape needs to have some initial value on it, for the TM to process.

Show
    Show will cause the machine to display its known rules, input and output languages, and its input tape.  This can be useful to see if a rule was not accepted for some reason.
Run
    Run will cause the machine to begin parsing the input tape.  A successful run ends with an "Accept" message.  An unsuccessful run ends in "Crash".
Input Language
    The language the machine can read or write to the tape.  Turing Machines, in general,  do not require that the input and output languages be identical.  This machine does.  This does not alter the computing power of the machine.
  Download the Java Source Code for this TuringMachine