The Turing Machine

Introduction
The Turing machine is one of the formalizations of a computing device. It has a finite control working on an infinite tape which - at every time - contains only finitely many nonblanc symbols. The update rules are easy and it is easy to see that a Turing machine is computable. Indeed it can be simulated on computers as done in this file. Church's Thesis says that also the converse is true: everything what can be computed in principal can also be computed by a Turing machine. This implementation contains the three machines from the lecture plus runs on sample input. The three implemented machines do the following:
  1. Interchanging all 0 and 1 in the input;
  2. Appending the first symbol at the end;
  3. Recognizing all palindromes over the alphabet {0,1}.
Further information on the Turing machine can be found on the Slides 10 to 22 for Lecture 8 (14.03.2007): ps-file; pdf-file.

The Turing machine in detail
The Turing machine uses the tape symbols "#" (for blank) and (potentially) "0", "1", "2", "3", "4", "5", "6", "7", "8", "9". Other symbols are ignored by this implementation. It is not necessary to fill the Turing table completely, but at those places not filled in, the machine might stop when it does not find the entry. All states are coded by two characters like "st" for starting state. The Turing table is coded as a sequence of entries "oosnna " where "oo" is the code for the old and "nn" for the new state. "s" is the code for the symbol and "a" for the activity. The letters "#","0", "1", "2", "3", "4", "5", "6", "7", "8", "9" stand for writing that symbol, "H" for halting, "L" and "R" for going left and right, respectively. When halted, the output is the word on the tape, it belongs to the duty of the programmer to make sure that the output has no spurious symbols "#" between its characters. There is no restriction where the output is standing on the tape.

A bit on the implementation
The function "tablecreate" generates an empty Turing table but reserves already entries for each state. Later the function "tableload" is used to load entries into the table. The third Turing machine uses these functions as follows. 
      tm = new tablecreate("stbrz1z2o1o2b1b2b3e1e2ha");
      tableload(tm,"st#brR br#ha1 br0z1R br1o1R ");
      tableload(tm,"z1#z2L z10z1R z11z1R z20b1# z21e11 ");
      tableload(tm,"o1#o2L o10o1R o11o1R o20e10 o21b1# ");
      tableload(tm,"b1#b2L b2#b3R b20b2L b21b2L ");
      tableload(tm,"b3#ha1 b30st# b31st# ");
      tableload(tm,"e1#ha0 e10e2# e11e2# e2#e1L ");
      tableload(tm,"ha0haH ha1haH ");
      var tape = new Array(" ","#","0","1","0","#"," ");
      turingrun(tm);
The function "tablecreate" does not only create an empty table but also declare that the used states are "st", "br", "z1", "z2", "o1", "o2", "b1", "b2", "b3", "e1", "e2", "ha". "st" is always the name of the starting state, but any other state can be any combination of two letters as long as that combination is declared when creating the table. It is recommended to avoid citation signs and special characters like linebreaks for names of states. The function "tableload" has two parameters, the Turing machine variable "tm" and a string of k*7 characters defining k entries for the Turing table. The format is explained above, for example "b31st# " stands for the following operation: 
      If the state is "b3" and the symbol on the tape "1"
      then write "#" and take the new state "st".
The tape is then assigned a list of symbols on the tape. The implementation treats blancs and "#" as the same type of symbols, but for better readability the first and last character are initialized as blancs and the others as "#". The call "turingrun(tm);" causes the Turing machine to run on the just defined tape content. Note that going up to the left border will cause "#" symbols to be inserted in the front which then shift the word right instead of moving the position left.

Java Script starts here.

Java Script ends here.