Please refer to this page for information on how to work on your assignment.
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.
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.
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.
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.