COMP4141 Assignment 3 (Part B) 2021 Term 1
Due: Monday, 12th April, 12:00 (AEST)
Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should
be typed, not handwritten. Use of LATEX is encouraged, but not required.
Discussion of assignment material with others is permitted at a high level, but the work submitted must
be your own in line with the University’s plagiarism policy.
Problem 1 (10 marks)
Suppose we define a deterministic two-stack PDA to be a machine with a finite stack alphabet, a finite set
of control states, and two stacks. Such a machine is initialised by loading the input into one of the stacks
(backwards, so that the left of the word sits at the top of the stack), and starting the machine in its initial
state. It then computes at each step of computation reading the top of the two stacks, and deterministically
performing a push or pop onto each of the stacks, and changing the control state. The machine has an
accept and a reject state. Show that two-stack PDA’s are equivalent to Turing machines: a language L is
accepted by some two-stack PDA iff it is accepted by some deterministic Turing Machine.
Problem 2 (10 marks)
Let Σ1 and Σ2 be disjoint sets. Say that a language L ⊆ Σ∗1 is decidably verifiable if there is a decidable
language L′ ⊆ Σ∗1 × Σ∗2 such that
L = {w : there exists c ∈ Σ∗2 such that (w, c) ∈ L′} (‡)
(a) Show that if L is recursively enumerable, then it is decidably verifiable. (4 marks)
(b) Show that if L is decidably verifiable, then it is recursively enumerable. (6 marks)
Observation
This is the “computable” analogue of the (polynomially) verifiable classification of NP. It is also
worth noting the similarity with Problem 5 in Assignment 2: using the notation from that problem,
condition (‡) can also be expressed as L = L′ ÷ Σ∗2 .
Problem 3 (10 marks)
Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer-
able? Justify your answer.
Return to start
Input: A Turing Machine M
Question: Is there an input which will make M return to its start state?
1
Remark
Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively
enumerable without determining if it is decidable)
Problem 4 (10 marks)
Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer-
able? Justify your answer.
NETM
Input: A Turing Machine M
Question: Is |L(M)| ≤ 1?
Remark
Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively
enumerable without determining if it is decidable)
Problem 5∗ (10 marks)
Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer-
able? Justify your answer.
SingletonTM
Input: A Turing Machine M
Question: Is |L(M)| = 1?
Remark
Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively
enumerable without determining if it is decidable)
2





















































学霸联盟