[plt-scheme] OT: not the halting problem, but what is it?

On Tue, May 4, 2010 at 9:37 AM, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:
>
> What you are doing is diagonalization, which as you point out is at the
> heart of Cantor's power set proof, and at the heart of the proof of the
> halting problem. The definition in step 2 ensures that the constructed
> function differs from any enumerated function on the argument which is its
> encoding. You've shown that there is no enumeration of total functions
> int->bool (and thus no programming language can express all such functions,
> even if the computational model guaranteed termination).

I think this just *is* Cantor's power set proof.  We've proved that we
can't put N into a bijection with N -> B, which is just a
representation of P(N).  But |P(N)| = |R|, so we've proved exactly
what Cantor proved.
-- 
sam th
samth at ccs.neu.edu