COSC1107/1105 Computing Theory – Tutorial 7 – Deadline: Sunday August 25th 2019, 11:59 PM
COSC1107/1105 Computing Theory
School of Computing Technologies
Semester 2, 2021
Tutorial No. 12: Revision and Review
Before this tutorial you are expected to have read the entire Computing Theory notes.
Aim
The aim of this tutorial is to explore more deeply the concepts which have been discussed in the past 11 weeks. You
will revise exercise based on Pumping Lemma, problem reduction, NFAs, DFAs, grammars and Turing Machines.
By the end of this tutorial you should be able to use the Pumping Lemma to show that a given language is not
regular. You should be able to build NFAs and DFAs from language specificaitons, create grammars and Turing
Machines.
Previous tutes?
Go over the last set of tutorials and make sure you cover them well. Have you done enough NFA to DFA conver-
sions? What about reductions? If you got them covered, then continue with the rest of this tute…
PART 1: Computability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Explain what decidable, undecidable, and semi-decidable problems are.
(b) The Halting Problem is the task of deciding whether given a Turing Machine M and an input string w,
whether M halts when run on input w. Prove that the Halting Problem is undecidable.
(c) Show, using problem reduction, that the following decision problems are undecidable:
i. Given a Turing machine M , decide whether M loops forever.
ii. Given a Turing machine M , decide whether M halts on the empty input (the blank tape problem).
iii. Given a Turing machine M , decide whether M halts on the input aaaaaaabbbbb.
(d) Why can’t we successfully argue that the blank tape problem is undecidable as follows: The blank tape
problem is a subproblem of the halting problem which is undecidable and therefore must be undecidable
itself.
(e) Are the following problems decidable? If yes, explain why. Otherwise, prove it is undecidable.
i. Given a TM M , does it ever reach a state other than its initial state if it starts with a blank tape?
ii. Given a TM M and a number n, does M have more than n states?
iii. Given a TM M and a non-halting state q of M , is there an input string w that would cause M to
eventually enter state q?
iv. Given a TM M , input w, and a number n, does M halt before n moves when run on input w?
v. Given a TM M , does it accept the empty string in an even number of moves?
vi. Given a TM M , is there a string it accepts in an even number of moves?
vii. Given a TM M , are there any input strings on which M loops forever?
viii. Given a TM M , does M halt within 10 moves on every string?
PART 2: Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
https://rmit.instructure.com/courses/79563/files/20012050?wrap=1
COSC1107/1105 – Computing Theory Tutorial 7: Revision and Review Page 2 of 3
(a) 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.
(b) 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.
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.
iii. Erase the b’s from the input – e.g. input configuration q0, BbabaababB will give an output of
qf , BaaaaB.
(c) 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.
ii. Given Σ = {S,X, Y, Z}. Erase the S’s from the input and replace all X’s with a, Y ’s with b and Z’s
with c. — e.g., input configuration q0, BY XSSSXY B will give an output of qf , BbaabB.
(d) Use the machines from c(i) and c(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.
PART 3: Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Match the following terms with the appropriate definition below: polynomial; polynomial time; decision
problem; problem instance; decider/decides; decideable; undecidable; semi-decideable; problem reduc-
tion; P; NP; NP-Complete; NP-Hard; tractable problem; intractable problem.
i. A transformation that changes instances of a decision problem into instances of a secondary decision
problem, whilst preserving the YES or NO output between problems (i.e. the YES or NO output of
the original problem/instance must be replicated by the output of the secondary problem/instance).
ii. Let M be a Turing machine that gives a correct YES or NO answer for every instance of decision
problem X . Then we say M is a decider for X , or M decides X .
iii. A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for
which in practice any solution takes too many resources to be useful.
iv. The set of decision problems that are elements of the set NP, and that can give a correct YES or NO
answer for every instance of every other problem in NP via a polynomial-time problem-reduction (i.e.
every other problem in NP can be reduced to them in polynomial time).
v. A decision problem coupled with a specific input appropriate to the problem, that requires a YES or
NO answer.
vi. The set of decision problems for which there exists a non-deterministic TM that will give a correct
YES or NO answer for every instance of the problem in polynomial time.
vii. A term to describe a decision problem, for which there does not exist a Turing machine, that will give
a correct YES or NO answer for every instance of the problem.
viii. A single question that requires a YES or NO answer, specific to each of a (potentially infinite) set of
inputs.
ix. A term to describe a decision problem, for which there exists a Turing machine, that will give a
correct YES or NO answer for every instance of the problem.
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) – James Harland Exercise 3 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 7: Revision and Review Page 3 of 3
x. A problem that can be solved in practice.
xi. An equation of the form f(x) = αnxn +αn−1xn−1 +αn−2xn−2 + …+α2×2 +α1×1 +α0x0, where
n ∈ N, and αi ∈ R, ∀ 0 ≥ i ≥ n.
xii. The set of decision problems for which there exists a deterministic TM that will give a correct YES
or NO answer for every instance of the problem in polynomial time.
xiii. The set of decision problems that can give a correct YES or NO answer for every instance of every
problem in NP via a polynomial-time problem-reduction (i.e. every problem in NP can be reduced to
them).
xiv. A term to describe the length of time taken by an algorithm requiring a number of computations that
is bounded by a polynomial function (T ) of the size of its input (n). This is true of a function T (n)
iff ∃c ∈ N, such that T (n) ∈ O(nc).
xv. A term to describe a decision problem, for which there exists a Turing machine, that will give a
correct answer for every instance of the problem that requires a YES, and that may give a correct
answer, or may give no answer at all, for instances of the problem that require a NO.
End of tutorial worksheet
RMIT CT 2021 (Semester 2) – James Harland