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.
Program completed.
Input is #010# .
Number State Position Symbol String Action New State
1 st 0 # #010# Right br
2 br 1 0 #010# Right z1
3 z1 2 1 #010# Right z1
4 z1 3 0 #010# Right z1
5 z1 4 # #010# Left z2
6 z2 3 0 #010# Write # b1
7 b1 3 # #01## Left b2
8 b2 2 1 #01## Left b2
9 b2 1 0 #01## Left b2
10 b2 0 # #01## Right b3
11 b3 1 0 #01## Write # st
12 st 1 # ##1## Right br
13 br 2 1 ##1## Right o1
14 o1 3 # ##1## Left o2
15 o2 2 1 ##1## Write # b1
16 b1 2 # ##### Left b2
17 b2 1 # ##### Right b3
18 b3 2 # ##### Write 1 ha
19 ha 2 1 ##1## Halt ha
Input is #011# .
Number State Position Symbol String Action New State
1 st 0 # #011# Right br
2 br 1 0 #011# Right z1
3 z1 2 1 #011# Right z1
4 z1 3 1 #011# Right z1
5 z1 4 # #011# Left z2
6 z2 3 1 #011# Write 1 e1
7 e1 3 1 #011# Write # e2
8 e2 3 # #01## Left e1
9 e1 2 1 #01## Write # e2
10 e2 2 # #0### Left e1
11 e1 1 0 #0### Write # e2
12 e2 1 # ##### Left e1
13 e1 0 # ##### Write 0 ha
14 ha 0 0 0#### Halt ha
Input is #0110110# .
Number State Position Symbol String Action New State
1 st 0 # #0110110# Right br
2 br 1 0 #0110110# Right z1
3 z1 2 1 #0110110# Right z1
4 z1 3 1 #0110110# Right z1
5 z1 4 0 #0110110# Right z1
6 z1 5 1 #0110110# Right z1
7 z1 6 1 #0110110# Right z1
8 z1 7 0 #0110110# Right z1
9 z1 8 # #0110110# Left z2
10 z2 7 0 #0110110# Write # b1
11 b1 7 # #011011## Left b2
12 b2 6 1 #011011## Left b2
13 b2 5 1 #011011## Left b2
14 b2 4 0 #011011## Left b2
15 b2 3 1 #011011## Left b2
16 b2 2 1 #011011## Left b2
17 b2 1 0 #011011## Left b2
18 b2 0 # #011011## Right b3
19 b3 1 0 #011011## Write # st
20 st 1 # ##11011## Right br
21 br 2 1 ##11011## Right o1
22 o1 3 1 ##11011## Right o1
23 o1 4 0 ##11011## Right o1
24 o1 5 1 ##11011## Right o1
25 o1 6 1 ##11011## Right o1
26 o1 7 # ##11011## Left o2
27 o2 6 1 ##11011## Write # b1
28 b1 6 # ##1101### Left b2
29 b2 5 1 ##1101### Left b2
30 b2 4 0 ##1101### Left b2
31 b2 3 1 ##1101### Left b2
32 b2 2 1 ##1101### Left b2
33 b2 1 # ##1101### Right b3
34 b3 2 1 ##1101### Write # st
35 st 2 # ###101### Right br
36 br 3 1 ###101### Right o1
37 o1 4 0 ###101### Right o1
38 o1 5 1 ###101### Right o1
39 o1 6 # ###101### Left o2
40 o2 5 1 ###101### Write # b1
41 b1 5 # ###10#### Left b2
42 b2 4 0 ###10#### Left b2
43 b2 3 1 ###10#### Left b2
44 b2 2 # ###10#### Right b3
45 b3 3 1 ###10#### Write # st
46 st 3 # ####0#### Right br
47 br 4 0 ####0#### Right z1
48 z1 5 # ####0#### Left z2
49 z2 4 0 ####0#### Write # b1
50 b1 4 # ######### Left b2
51 b2 3 # ######### Right b3
52 b3 4 # ######### Write 1 ha
53 ha 4 1 ####1#### Halt ha
Input is #0110010# .
Number State Position Symbol String Action New State
1 st 0 # #0110010# Right br
2 br 1 0 #0110010# Right z1
3 z1 2 1 #0110010# Right z1
4 z1 3 1 #0110010# Right z1
5 z1 4 0 #0110010# Right z1
6 z1 5 0 #0110010# Right z1
7 z1 6 1 #0110010# Right z1
8 z1 7 0 #0110010# Right z1
9 z1 8 # #0110010# Left z2
10 z2 7 0 #0110010# Write # b1
11 b1 7 # #011001## Left b2
12 b2 6 1 #011001## Left b2
13 b2 5 0 #011001## Left b2
14 b2 4 0 #011001## Left b2
15 b2 3 1 #011001## Left b2
16 b2 2 1 #011001## Left b2
17 b2 1 0 #011001## Left b2
18 b2 0 # #011001## Right b3
19 b3 1 0 #011001## Write # st
20 st 1 # ##11001## Right br
21 br 2 1 ##11001## Right o1
22 o1 3 1 ##11001## Right o1
23 o1 4 0 ##11001## Right o1
24 o1 5 0 ##11001## Right o1
25 o1 6 1 ##11001## Right o1
26 o1 7 # ##11001## Left o2
27 o2 6 1 ##11001## Write # b1
28 b1 6 # ##1100### Left b2
29 b2 5 0 ##1100### Left b2
30 b2 4 0 ##1100### Left b2
31 b2 3 1 ##1100### Left b2
32 b2 2 1 ##1100### Left b2
33 b2 1 # ##1100### Right b3
34 b3 2 1 ##1100### Write # st
35 st 2 # ###100### Right br
36 br 3 1 ###100### Right o1
37 o1 4 0 ###100### Right o1
38 o1 5 0 ###100### Right o1
39 o1 6 # ###100### Left o2
40 o2 5 0 ###100### Write 0 e1
41 e1 5 0 ###100### Write # e2
42 e2 5 # ###10#### Left e1
43 e1 4 0 ###10#### Write # e2
44 e2 4 # ###1##### Left e1
45 e1 3 1 ###1##### Write # e2
46 e2 3 # ######### Left e1
47 e1 2 # ######### Write 0 ha
48 ha 2 0 ##0###### Halt ha
Input is #01100110# .
Number State Position Symbol String Action New State
1 st 0 # #01100110# Right br
2 br 1 0 #01100110# Right z1
3 z1 2 1 #01100110# Right z1
4 z1 3 1 #01100110# Right z1
5 z1 4 0 #01100110# Right z1
6 z1 5 0 #01100110# Right z1
7 z1 6 1 #01100110# Right z1
8 z1 7 1 #01100110# Right z1
9 z1 8 0 #01100110# Right z1
10 z1 9 # #01100110# Left z2
11 z2 8 0 #01100110# Write # b1
12 b1 8 # #0110011## Left b2
13 b2 7 1 #0110011## Left b2
14 b2 6 1 #0110011## Left b2
15 b2 5 0 #0110011## Left b2
16 b2 4 0 #0110011## Left b2
17 b2 3 1 #0110011## Left b2
18 b2 2 1 #0110011## Left b2
19 b2 1 0 #0110011## Left b2
20 b2 0 # #0110011## Right b3
21 b3 1 0 #0110011## Write # st
22 st 1 # ##110011## Right br
23 br 2 1 ##110011## Right o1
24 o1 3 1 ##110011## Right o1
25 o1 4 0 ##110011## Right o1
26 o1 5 0 ##110011## Right o1
27 o1 6 1 ##110011## Right o1
28 o1 7 1 ##110011## Right o1
29 o1 8 # ##110011## Left o2
30 o2 7 1 ##110011## Write # b1
31 b1 7 # ##11001### Left b2
32 b2 6 1 ##11001### Left b2
33 b2 5 0 ##11001### Left b2
34 b2 4 0 ##11001### Left b2
35 b2 3 1 ##11001### Left b2
36 b2 2 1 ##11001### Left b2
37 b2 1 # ##11001### Right b3
38 b3 2 1 ##11001### Write # st
39 st 2 # ###1001### Right br
40 br 3 1 ###1001### Right o1
41 o1 4 0 ###1001### Right o1
42 o1 5 0 ###1001### Right o1
43 o1 6 1 ###1001### Right o1
44 o1 7 # ###1001### Left o2
45 o2 6 1 ###1001### Write # b1
46 b1 6 # ###100#### Left b2
47 b2 5 0 ###100#### Left b2
48 b2 4 0 ###100#### Left b2
49 b2 3 1 ###100#### Left b2
50 b2 2 # ###100#### Right b3
51 b3 3 1 ###100#### Write # st
52 st 3 # ####00#### Right br
53 br 4 0 ####00#### Right z1
54 z1 5 0 ####00#### Right z1
55 z1 6 # ####00#### Left z2
56 z2 5 0 ####00#### Write # b1
57 b1 5 # ####0##### Left b2
58 b2 4 0 ####0##### Left b2
59 b2 3 # ####0##### Right b3
60 b3 4 0 ####0##### Write # st
61 st 4 # ########## Right br
62 br 5 # ########## Write 1 ha
63 ha 5 1 #####1#### Halt ha
Input is #222# .
Number State Position Symbol String Action New State
1 st 0 # #222# Right br
2 br 1 2 #222# Error --
Input is #0121210# .
Number State Position Symbol String Action New State
1 st 0 # #0121210# Right br
2 br 1 0 #0121210# Right z1
3 z1 2 1 #0121210# Right z1
4 z1 3 2 #0121210# Error --
Input is #01221210# .
Number State Position Symbol String Action New State
1 st 0 # #01221210# Right br
2 br 1 0 #01221210# Right z1
3 z1 2 1 #01221210# Right z1
4 z1 3 2 #01221210# Error --