Re: Cardinality of Set of Computable Numbers?

From: Chan-Ho Suh (suh_at_math.ucdavis.nospam.edu)
Date: 12/26/03 

Date: Thu, 25 Dec 2003 16:50:05 -0800

In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>, Russell Easterly
<logiclab@comcast.net> 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.

Why is that? Can you exhibit a Turing machine to compute d?

In other words, you need a finite rule to compute this d. I don't
think you're going to find one.

> Therefore, S can't be the set of computable numbers.
>
[...]