Re: Cardinality of Set of Computable Numbers?

From: *** T. Winter (***.Winter_at_cwi.nl)
Date: 12/26/03 

Date: Fri, 26 Dec 2003 02:12:32 GMT

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

You are using that 'd' is computable, but for 'd' to be computable,
'f' should be computable. But 'f' is not computable, so 'd' is not
computable.

Losely said, a number is computable if there is a finite algorithm
that delivers that number. The number of finite algorithms is
countable, so the number of computable numbers is countable. But you
can not say for all finite algorithms in finite time whether they
deliver a number or do not stop. So there always remain algorithms
for which you do not know whether they must be in the list or not.
The conclusion is that you can not compute the list.

So, using your 'f' (which is not computable) you get a 'd' (which
is also not computable). 

-- 
*** t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~***/
Quantcast