/Users/billy/gits/moc-2021/problem-sets/solps12.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Selected Problem Set Solutions, Week 12
P12.1 See the Week 12 lecture slides.
P12.2 See the Week 12 lecture slides.
P12.3 (b) is not well-founded, as we can have infinite strictly decreasing sequences in Q, such as
1
1
, 1
2
, 1
3
, 1
4
, . . . . But (a), (c) and (d) are all well-founded. For (d) it may help to look at the
Hasse diagram for N× N ordered by ≺ (shown here in the margin).
(0, 0)
(0, 1)
(0, 2)
…
(1, 0)
(1, 1)
…
(2, 0)
(2, 1)
…
P12.4 hailstone :: Integer -> Int
hailstone 0 = 0
hailstone 1 = 0
hailstone n
| even n = hailstone (n `div` 2) + 1
| otherwise = hailstone (3*n+1) + 1
P12.5 Assume B is countable. Then we can enumerate B:
Element
b1 0 0 1 0 1 1 1 . . .
b2 1 0 1 1 1 0 1 . . .
b3 1 0 1 1 1 0 1 . . .
b4 0 1 0 0 1 0 0 . . .
…
However, the infinite sequence which has
i’th bit =
{
0 if the ith bit of bi is 1
1 if the ith bit of bi is 0
is different from each of the bi. Hence no enumeration can exist, and B is uncountable. This
should not be surprising, because the set B is really the same as (or is isomorphic to) N → Σ.