comp2022/2922 A3 (90 marks) – Turing Machines s2 2023
• Submission is on GradeScope.
– For problems 1 and 2, you will submit one PDF with your solutions.
– For problem 3, you will submit your TMs in files named problem
• This assignment is due in Week 10 on Sunday 15 October, 11:59pm.
3 1.txt,
problem 3 2.txt, problem 3 3.txt.
– For problem 4, you will submit files named run.sh, build.sh and other files you
require. The first argument of run.sh, either tm to ptm or ptm to tm, should choose
the solution that is run. A skeleton will be provided on Ed.
– For problem 5, you will submit your 2-tape TM in one file named problem 5.txt.
• All work must be done individually without consulting anyone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
• For clarifications and more details on all aspects of this assignment (e.g., level of justification expected, late penalties, repeated submissions, what to do if you are stuck, etc.) you
are expected to regularly monitor the Ed Forum post “Assignment FAQ”.
DTM stands for ”Deterministic Turing Machine”, and NTM stands for ”Nondeterministic Turing
Machine”.
All tapes in this assignment are doubly-infinite. When asked to give a low-level description use
Morphett’s format, and its extension to 2 tapes as follows: the instruction
q a b c d L R s
means that if the TM is in state q and reads a on the first tape and b on the second tape then it
writes c on the first tape and d on the second, and moves the first tape left and the second tape
right, and changes to state s.
For instance, suppose the question asked you to provide a 2-tape DTM that checks if a string has
the same number of 0s as 1s. Here is an answer:
; copy0: copies 0’s from tape#1 to tape#2
copy0 0 _ 0 0 R R copy0
copy0 1 _ * * R * copy0
copy0 _ _ * * L L compare
; compare: matches 1s on tape#1 with 0s on tape#2
compare 1 0 * * L L compare
compare 0 * * * L * compare
; same number
compare _ _ * * * * halt-accept
; more 1s than 0s
compare * _ * * * * halt-reject
; more 0s than 1s
compare _ * * * * * halt-reject
1
comp2022/2922 A3 (90 marks) – Turing Machines s2 2023
NB. The Morphett’s simulator only correctly simulates deterministic TMs. For nondeterministic
TMs it resolves nondeterminism randomly, which is not what TMs do! Thus, you cannot rely on
the simulator showing you all possible runs on a given input.
Problem 1. (20 marks)
1. (5 marks) Is the complement of every context-free language Turingdecidable? Give a brief justification of your answer.
2. (5 marks) Suppose that L is the intersection of a context-free language L1
and a regular language L2. Argue that L is in P. You may use any facts
proven in the lecture slides.
3. (5 marks) Fix Σ = {0, 1}. Consider the operation dub that maps a string
u to the string in which every 0 is replaced by 00. For a language L let
dub(L) = {dub(u) : u ∈ L}.
For instance, if L = {10, 1001, 11, ϵ} then dub(L) = {100, 100001, 11, ϵ}, and
if L = {0
n1
n
: n ≥ 0} then dub(L) = {0
2n1
n
: n ≥ 0}.
Suppose that L is decidable. Give a high-level description of a decider for
dub(L).
4. (5 marks) Consider the language L consisting of the set of strings
(SourceM1
, SourceM2
, SourceM3
) such that L(M1) is not regular, L(M2) is
not regular, and L(M1) ∪ L(M2) = L(M3).
Show that L is undecidable. You may only use facts from the lecture slides
to do so, e.g., that the acceptance problem TMs is undecidable.
Problem 2. (10 marks) Below is a NTM over input alphabet {a, b}.
1. (5 marks) Describe in one sentence the language that it accepts. Briefly
justify your answer. No marks will be awarded for describing how the TM
operates.
2. (5 marks) What is the asymptotic time complexity (aka running time) of
the NTM? Give your answer in big-Theta notation, and briefly explain your
answer.
; initial state is 0
; input alphabet is {a,b}
0 a a R 0
0 b b R 0
0 a A L 1
2
comp2022/2922 A3 (90 marks) – Turing Machines s2 2023
1 * * L 1
1 _ _ R 2
2 A A R 4
2 a _ R 2a
2a * * R 2a
2a A A R 2A
2A A A R 2A
2A a A L 1
2 b _ R 2b
2b * * R 2b
2b A A R 2B
2B A A R 2B
2B b A L 1
4 A A R 4
4 _ * * halt-accept
Problem 3. (20 marks) Fix Σ = {0, 1}.
1. (5 marks) Give a low-level implementation (in Morphett’s format) of a 1-
tape DTM that decides the language consisting of strings of the form x1y
where |x| = |y|. For instance, 1, 011, 10100 should be accepted, while
ϵ, 0, 00, 000, 11, 11000 should be rejected.
2. (5 marks) Give a low-level implementation (in Morphett’s format) of a 1-
tape DTM that decides the language consisting of strings of the form x1x.
For instance, 1, 010, 10110 should be accepted, while ϵ, 0, 00, 000, 11, 10101
should be rejected.
3. (10 marks) Give a low-level implementation (in Morphett’s format) of a 1-
tape DTM that decides the language consisting of strings of the form xyxxz
where x is non-empty. For instance, 1011, 000, 01110110110, 1001000010101
should be accepted, while ϵ, 0, 1101, 01101101, 0011101 should be rejected.
Problem 4. (20 marks) Following recent advances in interdimensional technology, a new type of Turing Machine has been developed, the portal Turing Machine
(PTM). These machines have the remarkable power to use 0 symbols on the tape
as portals, allowing them to traverse unbounded distances in a single step. (0
looks like a portal, you see.)
The semantics of a PTM are that when a machine is in a cell with a 0 and moves
left or right, instead of moving one cell, it moves to the next 0 in that direction.
3
comp2022/2922 A3 (90 marks) – Turing Machines s2 2023
If there is no 0 in that direction, it ”wraps around” the tape and moves to the 0
furthest in the other direction (eg. from the leftmost 0, a ”move left” instruction
moves to the rightmost 0). If there is only one 0 on the entire tape, a move left
or move right instruction causes it to stay put. Note that in each step, the write
instruction is executed before the movement instruction (since this may affect
whether a 0 is present when moving).
As a high ranking member of the Church of Turing, you want to uphold your
Thesis by showing that these new devices are equivalent in computational power
to traditional TMs.
1. (10 marks) Write a program to convert a basic TM into an equivalent PTM.
2. (10 marks) Write a program to convert a PTM into an equivalent basic TM.
Input will be a machine with input alphabet {0, 1}, tape alphabet {0, 1, , 2, 3},
all states other than the two halting-states (”halt-reject” and ”halt-accept”) are of
the form 0, 1, 2, · · · , 9 (i.e. states are single digit numbers and there are at most
10 non-halting states). Your output should be a machine with the same input
alphabet. The tape alphabet may be larger. Input and output machines are both
expected in Morphett’s format. Particularly, your output should start with the
state named 0 (zero).
For full marks, your simulating machines should have at most 100 states and be
reasonably efficient. Public tests and guidelines will be provided to judge this
efficiency.
Problem 5. (20 marks)
Build a 2-tape DTM S that takes as input an automaton A over input alphabet
{0, 1, #} on tape 1, and a string u ∈ {0, 1}
+ on tape 2, and accepts if u ∈ L(A),
and rejects otherwise. The TM S should run in polynomial time.
The input string u is guaranteed to be non-empty, but is otherwise an arbitrary
string the alphabet {0, 1}.
The states of our automata are denoted q1, q2, · · · , qn for some n. The initial
state is q1, and qn is the only final state (for simplicity). The automaton has
no epsilon transitions. Such an automaton will be represented as a string over
input alphabet {0, 1, #} as follows. The string encoding the automaton is of
the form u1u2 . . . un where each ui
is of the form #vi,1#vi,2# . . . #vi,n# where each
vi,j ∈ {00, 01, 10, 11} is defined as follows: the first bit of vi,j
is 1 iff the automaton
has a transition from qi
to qj on symbol 0, and the second bit of vi,j
is 1 iff the
automaton has a transition from qi
to qj on symbol 1.
You can assume that the input string to your TM is an encoding of an automaton,
i.e., the string matches the regular expression (#((0|1)
2#)
n
)
n
for some n. Subject
to this syntactic requirement, the automaton is otherwise arbitrary.
For example, the string
4
comp2022/2922 A3 (90 marks) – Turing Machines s2 2023
#11#10#00##00#00#01##00#00#11#
encodes the following NFA:
start q1 q2 q3
0,1
0 1
0,1
For full marks, your TM should have at most 100 states and be reasonably efficient. Public tests and guidelines will be provided to judge this efficiency.
Your TM should be written in the extension of Morphett’s format to 2-tape machines (described above).
10 marks are when A is a DFA, and 10 marks are when A is an NFA.