COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 5: Turing Machines
Before this tutorial you are expected to have read Section 5 of the Computing Theory notes.
The aim of this tutorial is to give you experience with Turing machines and to explore the concepts of language acceptors, transducers and universal Turing machines. By the end of this tutorial you should be able to specify more complex Turing machines, combine multiple Turing machines in a modular fashion and be able to represent a Turing machine as a binary string. You should also be able to use a Turing machine to accept a language, or produce an output for a given input.
PART1: TuringMachineFundamentals………………………………………………………… Turing machines are the most powerful formal computation mechanism known to man – Church’s thesis is that anything that can be computed by “mechanical” means can be computed by a Turing machine (there are other formal computational devices that are equivalent to Turing machines). The most important property that Church’s thesis provides is that we can provide mathematical proofs about computation – not just on simple machines but on any machine. In particular, there are some things that just can’t be computed – not just because machines are too slow or don’t have enough memory or we don’t know how to program it – it can be mathematically proven that some things just can’t be computed, period, by anything, ever! (This is all depending on accepting Church’s thesis as true, of course – Church’s thesis can’t be “proved” as such, the same way that a scientific theory can’t be proved – it can only be disproved, by finding a more powerful method of computation than Turing machines. However, there seems no reason to doubt it; yet.)
Note that adding extra features to a Turing machine does not alter it’s computational power – you can make them non- deterministic, give them an infinite tape in just one or both directions, add a stack, add an extra tape, make the tape 2-dimensional, etc., however, you won’t be able to compute anything that you couldn’t compute on the original machine!
In this tutorial we will consider Turing machines with a state based approach. This is very similar to the Finite Automata that you have already done.
Examples:
Let M be the following Turing machine with q0 as the initial state.
δBab
q0 q1 q2 q3 q4
q1,B,R
q2,B,L q1,a,R q1,b,R
q3,B,L q4,B,L q3,B,L q3,b,L q4,a,L q4,B,L
1. Give a state diagram for the above machine.
The figure below shows the state diagram. The conversion is pretty straightforward. Start from state q0, add the transitions for each input and then do the same for the next state and so on.
1
COSC1107/1105 – Computing Theory
Tutorial 5: Turing Machines
Page 2 of 7
a/a, R q3 b/b, R a/B, L
B/B, R B/B, L
q0 q1 q2
b/B,L
q4
a/B, L b/b, L
a/a, L b/B,L
2. Trace the computation of the string abab on this machine.
Always (unless specified otherwise) assume a start symbol (B) at the begining of the string and an infinite number of blanks (B) at the end. Before we do a trace it is important to understand exactly what is said in the table. For example it says at state q0 if the input is the start symbol B then go to state q1, write back B at the current position of the head and move the tape head to the right (R) to the next input. At state q1 if the input is B then go to state q2, write back B at the current position of the head and move the tape head to the left (L). At state q3 if the input is a stay in q3 and write a B at the current head position (i.e. overwrite the a with B) and so on.
The trace for the string abab is as follows.
q0, BababB ⊢ q1, BababB ⊢ q1, BababB ⊢ q1, BababB ⊢ q1, BababB ⊢ q1, BababB ⊢ q2, BababB ⊢ q4, BabaBB ⊢ q4, BabaBB ⊢ q4, BaBaBB ⊢ q4, BaBaBB
The first part of each line of the trace indicates the state the machine is currently in, with the head position being indicated by the underlined character. If you follow the Turing machine in a stepwise manner as above, tracing the computations is a trivial task. If you try to skip steps by trying to visualise it in your head what the answer will be, that is when problems can occur. So, it is always best to do a step-by-step complete traversal as above.
3. Explain the function of this Turing Machine.
If you look at the state diagram closely, you will notice that it first traverses the string all the way to the end and then works its way backwards. If the input at the end is an a then it changes all the as in the input to Bs and if it is b at the end it will change all the bs to Bs.
Questions:
(a) Let M be the following Turing machine with q0 as its initial state: abcB
q0 q1,B,R q1 q1,a,R q1,c,R q1,c,R q2,B,L q2 q3,c,L q3,b,L
i. Give the state diagram for M . Solution:
RMIT CT 2021 (Semester 2) –
Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 3 of 7
a/a, R b/c, R c/c, R
B/B, R B/B, L a/c, L
q0 q1 q2 q3
c/b, L
ii. Trace the computations for the input strings aabca and bcbc.
Solution:
q0, BaabcaB ⊢ q1, BaabcaB ⊢ q1, BaabcaB ⊢ q1, BaabcaB ⊢ q1, BaaccaB ⊢ q1, BaaccaB ⊢ q1, BaaccaB ⊢ q2, BaaccaB ⊢ q3, BaacccB
q0, BbcbcB ⊢ q1,BbcbcB ⊢ q1,BccbcB ⊢ q1,BccbcB ⊢ q1,BccccB ⊢ q1, BccccB ⊢ q2,BccccB ⊢ q3,BcccbB
iii. Describe the result of a computation in M (i.e the output).
(b) Draw the state diagram of a Turing machine that converts all bs to as and ds to cs. Assume that the input alphabet is {a, b, c, d}. Do this by:
i. Drawing the state diagram of a Turing Machine that converts all bs to as. Make sure that this machine finishes with the head pointing to the start of the tape.
ii. Drawing the state diagram of a Turing machine that converts all ds to cs. Solution:
Solution: All bs become cs except for the last character. If the string ends in a b or c, it is changed to b. However, if the last character is an a it is changed to c.
Solution:
a/a, R b/a, R c/c, R d/d, R
a/a, L b/b, L c/c, L d/d, L
B/B, R B/B, L
q0 q1 q2
RMIT CT 2021 (Semester 2) – Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 4 of 7
a/a, R b/b, R c/c, R d/c, R
B/B, R B/B, L
q0 q1 q2
iii. Combining these two machines such that the resulting machine changes all bs to as first and then replaces all ds to cs.
Solution:
.
a/a, R b/a, R c/c, R d/d, R
a/a, L b/b, L c/c, L d/d, L
a/a, R b/b, R c/c, R d/c, R
B/B, R B/B, L B/B, R B/B, L
q0 q1 q2 q3 q4
iv. Now, build a machine which does both conversions simultaneously, instead of combining two together.
(c) Draw the state diagram of a Turing machine which takes a string over {a, b} and changes every occurrence of the substring aba with bab. No changes are to be made to a string which does not contain aba. Also, once a change has been made, it should not change a newly created substring aba. For instance, in the string babaa, after changing babaa to bbaba, it should not change the underlined substring in bbaba.
Solution:
a/a, R b/a, R c/c, R d/c, R
B/B, R B/B, L
q0 q1 q2
Solution:
a/a, R
q0 q1 q2 q3 q4
b/b, R a/b, L b/a, L
q6
a/a, R b/b, R
Now, observe that due to looping transition B/B,R in q0, once the machine reaches the right hand side of the string, it will just keep going forever. Does it matter? The computation has still been performed, the aba’s have been changed to bab’s, however, it will never halt. In practical terms, would you like your machine to halt and clear the job that has been done? If so, how would you modify it slightly so that this happens?
a/a, R
b/b, R B/B,R
b/b, R
a/a, R b/b, R
a/b, R q5
(d) Consider the following Turing machine M .
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory
Tutorial 5: Turing Machines
Page 5 of 7
0/0,L 1/1,L α/α,L β/β,L q7
q0 B/B,R
0/0, R 1/1,R α/α, R β/β, R
0/α, L
q5
0/0, R q6 1/1,R α/α, R β/β, R
B/B, L
q1 q2 q3 q4
1/β, L
B/B, R
0/0, R 1/1, R
0/0, L 1/1, L
B/0, L
q8 q10
0/0, R 1/1, R α/α, R β/β, R
B/1, L
q9
0/0, R 1/1, R α/α, R β/β, R
0/0,L 1/1,L x/0,L y/1,L
i. Determine the tape output of M after it is given the following input: B01101001B. Try first to understand the
machine and postulate what the answer will be. Only list the computations as a last resort.
ii. Describe in one word, the function of M .
(e) Suppose our input alphabet is {1} and we represent a number n as (n + 1) 1s, i.e. zero is represented as 1, one is represented as 11, two as 111, so on and so forth. Construct a Turing machine that takes as input two numbers separated by a blank and adds them together. For example, input B111B1111B will give an output of B111111B.
(f) Build a Turing machine that enumerates the set of even length strings over {a}∗ (i.e., L((aa)∗) by writing them one after the other on the tape, each separated by a blank space (until the end of time!). You do not need to build it completely but enough to have a clear idea of what your machine would do and how.
Solution:
Solution:
B0110100101101001B
Solution:
Repeat, duplicate, copy, etc.
M takes any input and reproduces it after the input, leaving no blank space between the input and the copy.
Solution:
1/1, R 1/1, R
B/B,R B/1,R B/B,L 1/B,L 1/B,L
q0 q1 q2 q3 q4 q5
RMIT CT 2021 (Semester 2) –
B/0,L
1/y,R
x/x, R y/y,R
B/1,L
0/x, R
β/1,R
α/0, R
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 6 of 7
x/x,L q9 x ∈ {a,B,0}
q7 x/x,L
x ∈ {a,B}
q6
B/a,R Z/a,R q8
x/x,R
x ∈ {a,B,1} 0/1,R
B/Y,R Z/B,R
q3 q4 q5
x/x, R
x ∈ {a,B,0}
q0
B/Y,R B/Z,L
q1 q2
A Y is written to the tape to signify the left side of the computation, and a Z is written to signify the right. A counter of 1 symbols is kept just before the Y and aa is written to the tape (at the Z marker) for every 1 that is marked off (changed to 0). Once all 1s are changed to 0s, the current string being enumerated has been completed. This means the head reads the Y character, changes it to a 1, moves right, writes the Y again, before moving right along the tape, reseting all the 0s to 1s and moving the Z character one space right, to make space to start the next string in the enumeration. This continues forever and the machine will never halt.
This is one way of doing it, there are many others, but most of them either use a counter to keep track of the current length, or use the previous instance and add two more a’s in the next one. One needs to be careful not to destroy the data when using it (e.g., the previous instance) or to destroy it but then regenerate it. 🙂
(g) CompletethefollowingstepstoprovetheexpressivepowerofTuringmachinesisequivalenttothatof2-stackPDAs. i. Describe how a Turing machine can be designed to simulate a single stack PDA, and how this machine can be
modified to simulate a 2-stack PDA.
Solution:
A Turing machine can be designed to simulate a PDA with a single stack by treating the tape as a “stack” by first writing a symbol to the tape (here X) to signify the bottom of the stack, with the position of the head always pointing to the top of the “stack”. Deleting a symbol and moving the head left will simulate the “pop” operation and moving the head right and writing a symbol simulates the “push”.
For example, to “pop” A from the “stack”:
··· ···
“stack”
head
··· ···
“stack”
head
··· ···
“stack”
head
··· ···
“stack”
head
X
A
A
B
A
X
A
A
C
X
A
A
C
“stack”
head
And to “push” C onto the “stack”:
··· ···
X
A
A
C
X
A
A
C
RMIT CT 2021 (Semester 2) –
1/0,R
B/Z,L
B/Z,L
Y/1,L
1/0,R
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 7 of 7
head
··· ···
“stack”
Modifying this machine to simulate a 2-stack PDA is simple. The “stack bottom” symbol on the tape now functions to separate the two “stacks” and lets the machine know if either “stack” is empty:
head
··· ···
“stack 1” “stack 2”
When you want to switch between “stacks” you move the head all the way to the left until it reads a blank for “stack 1” or all the way to the right until it reads a blank for “stack 2”.
X
A
A
C
C
A
C
X
A
C
C
ii. Describe how a 2-stack PDA can be designed to simulate the function of a Turing machine.
Solution:
This is a bit trickier.
The idea is to define the transition function of the PDA in such a way that it simulates the Turing machine’s tape via the two stacks. One stack will be the symbols on the left of the simulated Turing machine’s head, while the second stack will be the symbols right of the head together with the one under the “head” of the PDA. The PDA initially writes the input string on the second stack in reverse order, so that the “head” starts over the left character of the input string.
For example, if the Turing machine we want to simulate starts with the string aabba on its tape, we need to initially push a B to each stack, to indicate the blank spaces on either side of the string, and then have tran- sitions that push the input string, in reverse order, to the second stack. So in this example the PDA will push a, b, b, a, a to stack 2 so it starts off looking like this, with the “head” pointing at the start of the string (arrows point to the top of the stack, where symbols get popped from):
“head”
a
a
b
b
a
B
B
stack 1
stack 2
Then, to simulate the “head” moving left-to-right along the tape, we can pop from stack 2 and push to stack 1, like so:
a
b
b
a
B
Ba
“head”
“head”
“head”
stack 1
stack 1
stack 1
stack 2
stack 2
stack 2
B
a
a
b
b
a
B
B
a
a
b
b
a
B
And then simulating the “head” moving right-to-left, we just do the opposite and pop from stack 1 and push to stack 2:
B
a
a
b
b
a
B
stack 1
stack 1
Ba
B
“head”
“head”
“head”
stack 2
stack 2
a
b
b
a
B
a
a
b
b
a
B
stack 1
stack 2
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 8 of 7
As the tape is infinite in both directions on a Turing machine, we need a way to simulate this as well. In order to give more room for computations, more Bs can be pushed to either end, just before the initial Bs that were pushed:
a
a
b
b
a
B
BB
“head”
“head”
stack 1
stack 1
stack 2
stack 2
B
B
B
a
a
b
b
a
B
This can be done as many times as needed, and therefore simulates the infinite tape on the left side of the input string. The same process can be performed for the other side of the “tape”, although you would have to shift all of the stack symbols from stack 2 to stack 1 first.
Obviously, we could also change the symbols on the “tape” as we moved the “head” around as well, by popping and pushing to stack 2 to perform computations.
iii. Describe the basic steps required for a A ⇒ B proof (where A and B are propositions).
Solution:
1. State what you are trying to prove
(e.g., prove ∀x ∈ Z, x is even ⇒ x2 is even)
2. Assume A is true
(e.g., let x ∈ Z, such that x is even)
3. Use assumption that A is true to derive B
(e.g.,x=2n,n∈Z,sox2 =(2n)2 =4n2 =2(2n2),hencex2 iseven)
4. Conclude that A ⇒ B
(e.g., Hence, ∀x ∈ Z, x is even ⇒ x2 is even. QED.)
iv. Describe the basic steps required for a A ⇔ B proof (aka: equivalence; if-and-only-if; iff).
Solution:
1. State what you are trying to prove
(e.g., prove ∀x ∈ Z, x is even ⇔ x2 is even)
2. ProveA⇒B
(e.g., prove ∀x ∈ Z, x is even ⇒ x2 is even)
3. ProveB⇒A
(e.g., prove ∀x ∈ Z, x2 is even ⇒ x is even)
4. ConcludethatasA⇒BandB⇒A,wehaveA⇔B
(e.g., Hence, as we have shown that ∀x ∈ Z,xiseven ⇒ x2 iseven and ∀x ∈ Z,x2 iseven ⇒ xiseven,wecansaythat∀x∈Z,xiseven⇔x2 iseven.QED.)
v. Combine your answers to (i), (ii) and (iv) to prove that the expressive power of Turing machines is equivalent to that of 2-stack PDAs.
Solution:
Proof:
Weneedtoprovethatforevery2-stackPDAM,thereexistsaTuringmachineTM suchthatL(M)=L(TM) andthatforeveryTuringmachineT,thereisa2-stackPDAMT suchthatL(T)=L(MT).Effectively,we must show that a Turing machine can simulate the function of a PDA (and therefore a 2-stack PDA) and also that a 2-stack PDA can simulate the function of a turing machine.
The proof of the first proposition is found in (i).
The proof of the second proposition is found in (ii).
Hence, as we have shown that a Turing machine can simulate the function of a PDA and also that a 2-stack PDA can simulate the function of a Turing machine, they must be equivalent. QED
PART 2: Universal Turing Machines…………………………………………………………….. A universal Turing machine is a Turing machine that can simulate the operation of an arbitrary Turing machine on an arbitrary input. As Turing machines can only accept symbols on a tape as their input; in order to achieve this, we must
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 9 of 7
first define a method of encoding a Turing machine in this way.
From Sudkamp (11.5):
A Turing machine (M) is defined by its transition function. A transition of a standard Turing machine has the form δ(qi,x) = [qj,y,d], where qi,qj ∈ Q; x,y ∈ Γ, and d ∈ {L,R}. We encode the elements of M using strings of 1’s.
Symbol Encoding
01 1 11 B 111
q0 1 q1 11 qn 1n+1
L1 R 11
Let en(z) denote the encoding of a symbol z. A transition δ(qi, x) = [qj , y, d] is encoded by the string: en(qi) 0 en(x) 0 en(qj) 0 en(y) 0 en(d).
The 0’s separate the components of the transition. A representation of the machine is constructed from the encoded tran- sitions. Two consecutive 0’s are used to separate transitions. The beginning and end of the representation is designated by three 0’s.
End Sudkamp (11.5)
Furthermore, the initial state is designated as q0, and acceptance is determined by halting. We denote the binary string representation of a TM M as R(M ).
(a) Let M be the Turing machine given below. Give the binary string representation R(M ). 0/1, R
1/0, R
q0 q1 q2
B/B, R
B/1, L 1/1, L
Solution:
000101110110111011001101011011011001101101101011001101110111011010011101101101101000
There are multiple correct answers for this question. Red zeros indicate the beginning and end of the tape and the gaps between transitions.
(b) The following three binary strings represent Turing machines:
R(MA ): 00010111011011101100110101101011001101101101101100110111011101110100 1110101111010110011101101111101101100111101110111011101000
R(MB ): 000111101110111011101001110110111110110110011101011110101100 110111011101110100110110110110110011010110101100101110110111011000
R(MC ): 000101110111011101100111010111010110011101101110110110011101110111101110100 1111010111110101100111101101111110110110011111011101111011101000
Red zeros indicate the beginning and end of the tape and the gaps between transitions.
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 10 of 7 i. Build Turing machine MA.
B/B, R B/B, L
q0 q1 q2
0/0, R 1/1, R
q3
q4
Solution:
ii. BuildTuringmachineMB.
B/B, R B/B, L
q0 q1 q2
0/0, R 1/1, R
q3
q4
Solution:
iii. BuildTuringmachineMC.
B/B, R B/B, L
q0 q2 q3
0/0, R 1/1, R
q4
q5
Solution:
iv. Are the strings R(MA), R(MB), and R(MC) unique? What about machines MA, MB and MC? Solution: The strings are all unique, however MA = MB and MA ̸= MC .
v. Explain why R(MA) ̸= R(MB), yet MA is identical to MB in every way.
vi. Explain why R(MA ) ̸= R(MC ), yet the function of MA is identical to the function of MC .
PART 3: Turing Machines as Language Acceptors………………………………………………. Turing machines can be used to accept any given (computable) language. In order for a Turing machine to accept a given input as a member of the language it must halt in a final state.
Build the following Turing machines.
(a) A machine that accepts strings of the form aba∗b
Solution:
Solution: The order in which the transitions are listed will change the binary representation, but will not change the Turing machine.
Solution: Changing state names will affect the binary representation, but will not alter the function of the Turing machine.
RMIT CT 2021 (Semester 2) –
0/0, R
B/B,L
0/0, R
B/B,L
0/0, R
B/B,L
1/1, R
1/1, R
1/1, R
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 11 of 7
a/a, R B/B,R a/a,R b/b,R b/b,R
B/B,R
q0 q1 q2 q3 q4 q5
B/B,L
(b) A machine that accepts {w ∈ {a, b, c}∗ | |w| is even }
(c) A machine that accepts {w ∈ {a, b, c}∗ | nw (a) = nw (b)}. Function nw (x) denotes the number of x’s in word w.
Solution:
B/B,R a/a,R;b/b,R;c/c,R
q0 q1 q2
a/a, R; b/b, R; c/c, R
Solution:
Here is one solution; of course there are others.
q6
a/a, R c/c,R Y/Y,R
q2
X/X,R
b/b,L q5 c/c,L
X/X,L
q0
B/B,R
b/b,R
Y/Y,R X/X,R c/c,R
q1
a/a, L q3 c/c,L
Y/Y,L
c/c,R q4 X/X,R
A link to the JFLAP file for this machine is here (this machine has been modified so that the head starts on the first character of the input string, not the first blank to make testing strings easier.)
(d) A machine that accepts {aibj | i ≥ 1,j ≥ 0,i ̸= j}
Solution:
One such machine is below. The idea is that we check if the input only a’s, in which case we accept. Otherwise, we mark each a with an X and attempt to find a matching b (marked with Y ). If we can do this for all as and bs, we reject the string; otherwise we accept it.
RMIT CT 2021 (Semester 2) –
B/B,R Y/Y,R
b/Y,L
a/X,R
b/Y,R
a/X,L
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 12 of 7
a/a, R
q0 q1 q2 q3 q4
B/B, R a/a, R
b/b, R
a/a, R Y/Y,R
a/a, L Y/Y,L
B/B, L
a/a, L b/b, R b/b, L
q6
b/Y,L q5
B/B,R
q7
q9
b/b, R
Y/Y,R
q8 Y/Y,R
(e) A machine that accepts {ai bj ai+j | i, j ≥ 0}
Solution:
One solution is below, which converts the initial as and bs to Xs and then checks that the number of Xs is equal to the number of as (i.e., it converts the string to Xi+jai+j).
a/X, R b/X, R a/a, R a/a, L, X/X, L B/B,R b/X,R a/a,R B/B,L a/Y,L
q0 q1 q4 q5 q6 q7 q8 B/B,R
a/a, R, X/X, R
X/Y,R
q9
B/B,L Y/Y,R X/X,L
Y/Y,R
Y/Y,L
q2
q3 q10
X/X,L
A link to the JFLAP file for this machine is here (this machine has been modified so that the head starts on the first character of the input string, not the first blank to make testing strings easier.)
PART4: TuringMachinesasTransducers………………………………………………………. Turing machines can also be used to perform computations on an input string. When used as a transducer in this way, a Turing machine is producing an output on its tape, for some given input, and therefore does not require a final state. As it is not accepting or rejecting its input, which state it halts in (if it must halt at all) is not important.
(a) Construct a Turing machine with input alphabet {a, b} to perform each of the following operations. Note that the tape head is scanning position zero in state qf whenever a computation terminates.
i. Move the input one space to the right – i.e. for input configuration q0, BuB the output configuration should be qf , BBuB.
RMIT CT 2021 (Semester 2) –
a/X, R
X/X, R
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 13 of 7
q0
q7
B/B,R
x/B,L,
x ∈ Σ ∪ {B}
q1
q6
q2
q4
x/B,L,
x ∈ Σ ∪ {B}
q3
q5
a/a,R b/b,R
Solution:
ii. Concatenate a copy of the reversed input string to the input — e.g, input configuration q0,BuB will give an output of qf , BuuRB.
Solution:
B/B,R
q0 q1
a/X,R b/Y,R
B/a,L B/b,L
X/a,R Y/b,R a/a, L
b/b,L
a/a, R
b/b,R b/b,R
q3 q2 q4
a/a, R
iii. Erase the b’s from the input – e.g. input configuration q0, BbabaababB will give an output of qf , BaaaaB.
Solution:
b/b,R
B/B,R B/B,L
q0 q1 q4
a/a, L b/B,L
b/b,L q2
q3
B/B,R a/a, R
(b) Construct a Turing machine to perform each of the following operations. Note that the tape head is scanning position zero in state qf whenever a computation terminates.
i. Given Σ = {a, b, c}. Replace any occurrence of the string abc with SSS and replace all other a’s with X, b’s with Y and c’s with Z — e.g., input configuration q0, BbaabcabB will give an output of qf , BY XSSSXY B.
Solution:
RMIT CT 2021 (Semester 2) –
x/b, L,
x ∈ Σ ∪ {B}
b/b, R
a/a, R
x/a, L,
x ∈ Σ ∪ {B}
B/B,L
b/a,R
B/B,L
a/b, L
B/B,R
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 14 of 7
S/S,R
b/Y,R x/x,L, c/Z,R ∀x ∈ {S,X,Y,Z}
B/B,R B/B,L q0q1 q6
q5
q4
q2
q3
a/X,R
c/S,L
A link to the JFLAP file for this machine is here (this machine has been modified so that the head starts on the first character of the input string, not the first blank to make testing strings easier.)
ii. GivenΣ={S,X,Y,Z}.ErasetheS’sfromtheinputandreplaceallX’switha,Y’swithbandZ’swithc.— e.g., input configuration q0, BY XSSSXY B will give an output of qf , BbaabB.
Solution:
S/S,L q3
q4
S/B,L x/x,R, q2 x/x,L,
∀x ∈ {a,b,c,B}
∀x ∈ {a,b,c}
q0
B/B,R
S/S,L q5
q6
q7 S/S,L
q1 S/S,R
q8
x/x,R,
∀x ∈ {a,b,c,B}
A link to the JFLAP file for this machine is here (this machine has been modified so that the head starts on the first character of the input string, not the first blank to make testing strings easier.)
(c) Use the machines from b(i) and b(ii) to construct a Turing machine with input alphabet {a, b, c} that deletes any occurence of the string abc in the input string1. For instance, with input configuration q0,BbaabcabB the output configuration would be qf , BbaabB.
Solution:
1However, do not worry if this forms abc somewhere in the output string, such as removing abc from the input string aabcbca.
RMIT CT 2021 (Semester 2) –
a/X,R c/Z,R
X/S,R
B/B,L
b/Y,R
Y/S,L
a/X,R
B/B,L
X/S,L
Z/S,L
B/B,L
Y/S,L
S/b,R
b/Y,R
x/x,R,
∀x ∈ {a,b,c,B}
S/c,R
S/a,R
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 15 of 7
S/S,L q9 b/Y,R x/x,L,
q10
S/B,L x/x,R, q8 x/x,L,
∀x ∈ Σ ∪ {B}
∀x ∈ Σ
S/S,R
c/Z,R ∀x ∈ {S,X,Y,Z}
S/S,L q11
q12
q13 S/S,L
B/B,R B/B,L B/B,R
q0q1 q6q7S/S,R
q5
q4
q2
q3
a/X,R
q14
c/S,L
x/x,R,
∀x ∈ Σ ∪ {B}
NB: Make sure you are careful to change the input alphabet for the second machine to {a, b, c} from {X, Y, Z, S}.
A link to the JFLAP file for this machine is here (this machine has been modified so that the head starts on the first character of the input string, not the first blank to make testing strings easier.)
PART5: Homework…………………………………………………………………………….. (a) How could you execute the Towers of Hanoi algorithm on a two-stack PDA? (Hint: it will suffice to show how you
can swap the positions of two adjacent elements of one of the stacks).
Solution: One can use three stacks, one for each tower, however this is not necessary (2 stack PDA is equivalent to a turning machine). A possible solution is to keep one stack which contains the position of each ring. It would start of something like:
Stack A B 0
0
0
0
where the bottom of the stack signifies the largest ring and the top signifies the smallest. In order to move a ring to a different stack (ie, from 0 to 2), simply pop until you find a ring on the source stack (storing intermediate values on stack B), and then replace that with the new value:
Stack A B 2
0
0
0
next move:
Stack A B – A B – A B 2
011 000 02020
and so on. You could have an input string which contains the moves to make as pairs of numbers. eg, a solution for the four ring towers would be: 010212012021010212102012010212 and the final state:
RMIT CT 2021 (Semester 2) –
X/S,L
Z/S,L
B/B,L
Y/S,L
S/b,R
a/X,R c/Z,R
X/S,R
B/B,L
S/c,R
S/a,R
b/Y,R
Y/S,L
a/X,R
B/B,L
x/x,R,
∀x ∈ Σ ∪ {B}
b/Y,R
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 16 of 7
Stack A B 2
2
2
2
and the machine would simply pop until it found the first number, then change it to the second number.
(b) Construct a Turing machine that copies all the symbols from the current head position up to the first blank back over to the start of the tape. So if the input string was “hello there ted”, and the head was at the first “t” the output would be “there there ted” (Note: it doesn’t delete what was on the tape after the part that is overwritten).
State any assumptions that you use to build your machine.
Solution: The hash symbol keeps track of the current position of the source (string to be copied), and the star symbol keeps track of the number of letters copied to the target. The machine then copies a letter from the source, puts a hash in that position, goes back in search of start, overwrites the star with the new letter and writes another star next to it so that the machine knows where to come back to for the next letter.
We assume the input string is built over alphabet {a, · · · , z, $}, where $ denotes the (blank) space symbol, which is different from the blank symbol B used to denote an empty tape cell (and to delimit the start and end of the input string). Below l ∈ {a, · · · , z}, that is l is any lower case letter.
l/l, L l/l, R T/#,L B/B,R T/T,R S/∗,R
q0 q1 q2 q3 q4 #/T,R
q7 q6 q5
S/∗, R
∗/S, L
$/$, L B/B,L
l/l, L
q8 l/l, L
∗/T,R
q9
T/#,L
Now, the “idea” of the machine as a strategy is “correct,” but there is a major error or misunderstanding with it. Observe symbols T and S. What are they? First of all, they are not symbols one could find on the tape, so they are just placeholders. One would say that they are any letter in {a, . . . , z}. However, this would mean that they are “remembered” by the machine in subsequent transitions, and this cannot happen!
So, really the machine above is just a “template” of the actual machine, where one has to instantiate each T and S with each letter {a, . . . , z} and generate new (sub)machines for each of the combination.
For example, there is not just one transition from q0, there are one per letter a to z going to particular states q1a
to q1z. Then, state q1x is the state q1 remembering that the letter to be copied is x. Similar thing happens with placeholder S.
Problem:
The following is an interesting problem I found in the book Introduction to Computer Theory (2nd edition), by , Wiley, 1997. See what you think …
“(Oddly enough, this problem has nothing to do with computer theory, yet it has everything to do with the contents of this chapter).
In the English language, we can observe that some adjectives apply to themselves. For example, the word “short” is a fairly short word. We mighy say, “short” is short. Also, the adjective “polysyllabic” is indeed polysyllabic. Some other
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 5: Turing Machines Page 17 of 7
possible adjectives of this type are “unfrequent”, “melodious”, “arcane”, “unhyphenated”, “English”, “non-palindromic”, and “harmless”. Let us call all these adjectives that describe themselves homothetic. Let us call all other adjectives (those that do not decribe themselves) heterothetic. For example, the words “gymnastic”, “myopic”, and “recursive” are all heterothetic adjectives The word “heterothetic” is an adjective, and therefore like all adjectives it is either homothetic or heterothetic. Which is it? ”
You may need some help to figure this one out …
Reflection:
Consider the HALTEMPTY decision problem: Given a Turing machine M , does M halt on the empty input (i.e., does M halt on input ε)? Do you think that HALTMEPTY is decidable? What does it mean to be decidable? Why could it be? Why could it not be? Just discuss this informally with your peers….
You will recall the April 1984 edition of TIME magazine, and the quotation below:
“Put the right kind of software into a computer, and it will do whatever you want it to. There may be limits on
what you can do with the machines themselves, but there are no limits on what you can do with software.”
What do you think about this statement now?
What is the significance of the Universal Turing machine?
End of tutorial worksheet
RMIT CT 2021 (Semester 2) –