Assignment 18 - The Turing Machine

You can download this homework and set the permissions with the commands

      cd ~/public_html
      wget http://www.comp.nus.edu.sg/~gem1501/assignment18.html
      chmod 755 *.html

Outline
This is an implementation of the Turing Machine. The implementation itself is already completed but the Turing Machine which is interpreted by the Java Script Program should be updated. You find a Turing Machine which computes the following function:

      Input:  A word consisting of digits 0 and 1,
      Output: 1 if the word is a palindrome,
              0 if it is not a palindrome.

The task is to modify the table of the Turing machine such that palindromes consisting of the digits 0, 1 and 2 are properly accepted. Besides of the table of the Turing machine, nothing has to be edited.

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. More explantion on the Turing machine is found on the Slides 8 to 17 for Lecture 8 (11.03.2005): ps-file; pdf-file.

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 current implementation uses these functions as follows.

      var 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.

What has to be done
The current implementation recognizes palindromes over the alphabet {0,1}. The task is to extend the Turing machine such that it recognizes palindromes over the alphabet {0,1,2}. For achieving this, new states have to be introduced and further entries be added to the Turing table. So one has to edit the CALLS of the functions "tablecreate" and "tableload" but NOT the IMPLEMENTATION of these functions. In the call of "tablecreate" the names of the new states have to be added and in the calls of "tableload" new entries dealing with the symbol "2" have to be added. Perhaps it is also convenient to add some calls of "tableload" in order to get these calls not to become too lengthy. There are three test runs containing inputs using the symbol "2" as well and the machine should behave correctly on these inputs.

Java Script starts here.

Java Script ends here.