Copyright © University of Cambridge. All rights reserved.

'Binary Sequences' printed from

Show menu

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.