Age 16 to 18 Challenge Level:
A miraculous machine tosses a coin an infinite number of times in
one second and the result is recorded as an infinite sequence of
zeros and ones (one for a head and zero for a tail). Suppose the
machine is reset and the tosses of the coin for the next second are
recorded in the same way. Further suppose that the machine goes on
doing this for ever. The record of the results is an infinite set
of infinite binary sequences.
Show that there is some sequence of tosses that is never recorded
by the machine.
Show that the infinite set of finite (or terminating) binary
sequences can be written as an ordered list whereas the infinite
set of all infinite binary sequences cannot.