/Users/billy/gits/moc-2021/problem-sets/ps12.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 12
18–22 October 2021
Content: Undecidability, reductions, well-founded relations, termination
P12.1 Show that
ETM = {〈M〉 | M is a TM and L(M) = ∅}
is undecidable. Hint: We know that ATM is undecidable. Show that if ETM was decidable,
then ATM would be decidable.
P12.2 Show that
EQTM = {〈M1,M2〉 | M1,M2 are TM s and L(M1) = L(M2)}
is undecidable. Hint: Use the fact that ETM is undecidable.
P12.3 Recall that a binary relation ≺ over set S is a well-founded relation iff there is no infinite
sequence s0, s1, s2, s3, . . . such that si ≻ si+1 for all i ∈ N. That is, each sequence of elements
from S, when listed in decreasing order, is finite. For each of the following, say whether it is
well-founded:
(a) The usual “smaller than” relation, <, on the natural numbers N.
(b) The usual “smaller than” relation, <, on the rational numbers, Q.
(c) The relation “is a proper sublist of” on the set of finite lists.
(d) The (strict) lexicographic ordering of pairs of natural numbers, that is, the relation ≺
defined by (m,m′) ≺ (n, n′) iff m < n ∨ (m = n ∧m′ < n′).
For the last question, it may help to draw the Hasse diagram for the partially ordered set
N× N, ordered by �, the reflexive closure of ≺.
P12.4 (Optional.) Consider the function c : N →֒ N, defined recursively like so:
c(n) =
1 if n = 0 or n = 1
c(n/2) if n is even and n > 1
c(3n+ 1) if n is odd and n > 1
Write a Haskell function hailstone :: Integer -> Int which calculates the number of
recursive calls made when computing c(n). For example, hailstone 5 should evaluate to 5,
and hailstone 27 should evaluate to 111.
c is known to terminate for all natural numbers up to 1020. It is conjectured to terminate for
all n ∈ N, but whether this is is actually the case is an open problem. There are examples
where similar conjectures have been refuted. One famous example has to do with prime
factorisations. Say that n > 1 is peven if its prime factorisation has an even number of
factors; otherwise n is podd. So 28 = 2 · 2 · 7 is podd, and 40 = 2 · 2 · 2 · 5 is peven. Pólya
conjectured that, for any k, the set {2, 3, 4, . . . , k} never has a majority of peven elements.
However, that turned out to be false, the smallest counter-example being k = 906150257.
P12.5 (Optional.) Consider the alphabet Σ = {0, 1}. The set Σ∗ consists of all the finite bit strings,
and the set, while infinite, turns out to be countable. (At first this may seem obvious, since
we can use the function binary : N → Σ∗ defined by
binary(n) = the binary representation of n
as enumerator; however, that is not a surjective function, because the legitimate use of leading
zeros means there is no unique binary representation of n. For example, both 101 and 00101
denote 5. Instead the idea is to list all binary strings of length 0, then those of length 1, then
those of length 2, and so on: ǫ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, . . ..)
Now consider instead the set B of infinite bit strings. Show that B is much larger than Σ∗.
More specifically, use diagonalisation to show that B is not countable.