Assignment 19 - The Turing Machine

1. Getting Started

   Please refer to this page for information on how to work on your assignment.

2. Outline

   This is an implementation of the Turing machine. The implementation itself is already completed but the Turing machine which is interpreted by the JavaScript 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. Aside from the table of the Turing machine, nothing has to be edited.

3. The Turing machine in detail

   The Turing machine uses the tape symbols # (for blank) and (potentially) 0 to 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 the starting state. The Turing table is coded as a sequence of entries such as oosnna (with a trailing space character) where oo and nn are respectively the codes for the old state and the new state. s is the code for the symbol and a the code for the activity. The symbols # and 0 to 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 on where the output has to stand 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.

4. A bit on the implementation

   The tablecreate() function generates an empty Turing table but reserves entries for each state. Later the tableload() function 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 tablecreate() function 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 tableload() function 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 to 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.

5. 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 to the tablecreate() and tableload() functions but NOT the IMPLEMENTATION of these functions. In the call to 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 to tableload() in order to not get these calls 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.