Re: Cardinality of Set of Computable Numbers?

From: Barb Knox (see_at_sig.below)
Date: 12/29/03 

Date: Mon, 29 Dec 2003 14:24:18 +1300

In article <19idnd3Ywuot6HKiRVn-sA@comcast.com>,
 "Russell Easterly" <logiclab@comcast.net> wrote:

>"Pento" <robby.goetschalckx@student.kuleuven.ac.be.NOSPAM> wrote in message
>news:Xns945F820BCBD74robbygoetschalckxstu@134.58.127.12...
>> "Russell Easterly" <logiclab@comcast.net> wrote in
>> news:Bu-dnYP-tIz1JHOiRVn-sA@comcast.com:
>>
>
>> OK, consider the set of natural numbers, N.
>> Also consider the operation "+ 1".
>>
>> Is it not true that for each n in N, n + 1 is also in N ?
>
>Maybe.
>I might not be the person you want to ask this question to.
>My proof shows that no set can contain every computable
>natural number. If N does not contain every computable
>natural number, how can we say N contains all natural numbers?

(I haven't been following this thread, so please make allowances if what
I say here is either redundant or irrelevant.)

The standard definitions of "computable" are equivalent to "computable
by some Turing machine". Now clearly, each particular natural number K
can be generated by some TM; indeed, it's even computable by a
finite-state machine (with K states).

Furthermore, the infinite sequence of all natural numbers together
(e.g., in base 1, 010110111011110111110...) can be generated by a
(non-halting) TM -- the algorithm repeatedly copies the last string of
1's (which can be done finitely by temporarily replacing the most recent
1 copied with some other symbol, to keep track of how much has already
been copied) and writes an extra 1.

So in what sense isn't every natural number computable?

[snip] 

-- 
---------------------------
|  BBB                b    \     Barbara at LivingHistory stop co stop uk
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   
|  B  B  a  a   r     b  b  |   
|  BBB    aa a  r     bbb   |   
-----------------------------