CS计算机代考程序代写 /Users/billy/gits/moc-2021/problem-sets/solps12.dvi

/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 → Σ.