Re: Cardinality of Set of Computable Numbers?

From: Stephen Montgomery-Smith (newsmail_at_cauchy.math.missouri.edu)
Date: 12/26/03 

Date: Fri, 26 Dec 2003 08:27:18 GMT

Russell Easterly wrote:
> As often happens, I have managed to confused myself.
> Any enlightenment will be appreciated.
>
> I have read that the set of computable numbers is countable.
>
> Let S be the set of all computable numbers
> and assume S is countable.
>
> Since S is countable there is a function, f(),
> that maps S to the natural numbers.
> Using f() to order S, define a diagonal number, d.
> d is a computable number not in S.
> Therefore, S can't be the set of computable numbers.
>

The problem is that there is no function f, as you describe, that is computable.
  Why? Well, you just provided the proof.

In fact, you have provided a rather roundabout way of proving Turing's halting
theorem (because there is an 'obvious' way to try to make a computable f - e.g.
interprete the number as a computer program in ASCII code, and run that program).