Infinite Sets; Russell's Paradox; the Halting Problem

     INFINITE SETS

When S is a finite set, we defined |S| -- the cardinality of S -- as
the number of elements in S. Thus |S| is a natural number: 0 or 1 or 2
etc.  But what if S is infinite?

There is a rich theory of cardinality of infinite sets, and we will
see a tiny piece of it later on. For now we simply point out that many
of the most important sets in mathematics and computer science are
infinite: N, Z, Q, R, the set of primes, the set of programs that can
be written in a given language, etc.


     RUSSELL'S PARADOX

This however can quicky lead into very bizarre situations, as we will
now consider. Let UU be the set of ALL sets; note that UU then is an
element of itself.  (For any worriers, simply note that the notion of
self-membership is not necessarily complete nonsense.  For instance, a
book that consists of a list of all book titles published so far might
well list itself. And it is very common for a book to refer to itself
in its preface.) UU is infinite, of course.  And UU =/= {UU}; the
latter set is finite, with cardinality = 1. Also UU^c = emptyset; and
UU^c is an element of UU.

Now consider the set S consisting of all sets that contain themselves
as elements; so UU is an element of S, for example. Another example is
the set Inf of all infinite sets. Clearly Inf is infinite (there are
infinitely many infinite sets), so Inf is one of those sets that are in
Inf, so it belongs to itself and hence it is an element of S.

Finally, S^c = U-S, the set of all sets that do NOT contain themselves
as elements.  Most sets that we make use of are in S^c: N, Q, R, Z,
{1,2,3}, etc; but these are not elements of S^c: Inf, S.  Also, S^c is
an element of Inf, since S^c is infinite; and S^c is an element of UU
of course, since it is a set.

Two questions: 

(i) Is S^c in S? That is, is S^c an element of itself?  If so, then
it is one of those sets that do not contain themselves, i.e., S^c is not
in S^c. But we can't have S^c in S^c and also S^c not in S^c!  So "S^c
in S^c" must not hold. 

(ii) Is S^c then not in S^c? We just said so!  But then S^c is not one of those
sets that contain themselves, and that means it is not in S; but then
it must be in U-S = S^c!  So also "S^c not in S^c" cannot hold.

We have just seen Russell's Paradox!

The lesson here is that one must be careful in using ideas about sets
when the sets in question are "strange".  But just what the
strangeness is and how it arises -- and what to do about it -- is the
subject of much controversy.


     THE HALTING PROBLEM

Let p be a program and d data, and write p(d) to mean the output from
p when running on data input d.

Alan Turing described this problem in 1936: devise a program h, with
the property that it takes as input two files (the first one of which
is some program code p, and the second is data d that first file can
use), such that: 

(i) If p running on d would in fact eventually complete it execution
and halt, then h running on (p,d) outputs "halt" and halts

(ii) If p running on d would loop foreverm then h running on (p,d)
outputs "loops" and halts

The idea is that such an h would be an automatic infinite-loop
detector, telling us whether a given program running on given data
would eventually finish, or loop forever. It woudl be a very useful
program, saving lots of time and money.

But in that same paper, Turing proved this:

Theorem (Turing) "Unsolvability of the Halting Problem": There can be
no such program as h above.

Proof: By contradiction. Suppose in fact h were a program
with properties (i) and (ii) above. Then let T be this program, that
accepts code as input:

==========

t(p):  
  if h(p,p)="halt" then  [[ comment: here h(p,p) is a call to h running on (p,p) ]]
	print "ha-ha-ha" forever
  if h(p,p0="loops" then halt
==========

Now run t(t,t).  If h(t,t)="halts" then t(t) doesn't halt (so h is
"wrong"). And if h(t,t)="loops" then t(t) halts, so again h is wrong.