School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 12
18–22 October 2021
Content: Undecidability, reductions, well-founded relations, termination The exercises
T12.1 Show that the halting problem for Turing machines is undecidable. More precisely, show that the language
HaltTM = {⟨M,w⟩ | M is a Turing machine and M halts when run on input w}
is undecidable. Hint: Use reduction from ATM , that is, show that if we did have a decider
for Halt TM then we could also build a decider for ATM . Continued in P12.1 & P12.2
T12.2 Let M be a Turing machine with alphabet Σ and w ∈ Σ∗ a string. Define a language A containing only the single string s, where
s=1 ifM haltsoninputw
0 ifM doesnothaltoninputw
Is A decidable? Why or why not?
T12.3 Consider the problem of whether a given context-free grammar with alphabet {0,1} is able
to generate a string in L(1∗). Is that decidable? In other words, is the language {⟨G⟩ | G is a context-free grammar over {0,1} and L(G) ∩ L(1∗) ̸= ∅}
decidable? Show that it is decidable, using a decider ECFG for the decidable language {⟨G⟩ | G is a context-free grammar over {0,1} and L(G) = ∅}
Hint: Consider known closure properties for context-free languages.
Continued in P11.7 & P11.8
T12.4 You have a bag of (n > 0) coloured marbles. There are three colours: red, blue, and white, and on the table, next to the bag, is a huge box with marbles of all three colours, enough
that you never run out. Now repeat the following process:
(a) If the bag contains at most one marble, halt; otherwise remove two marbles from the bag (without looking).
(b) If one of the two marbles is red, move both to the box.
(c) If both are white, put one of them back into the bag, together with 5 blue marbles from the box (the other white marble goes in the box).
(d) Otherwise move both to the box, and move 10 red marbles from the box to the bag.
Define a well-founded relation on a set of configurations, and use this to prove that the process must halt.
Continued in 12.3