Re: Cardinality of Set of Computable Numbers?

From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 12/26/03 

Date: 26 Dec 2003 15:33:46 -0500

"Russell Easterly" <logiclab@comcast.net> writes:
 : Let a computable number be defined as the unbounded, but finite output tape
 : of a TM.

That's possible but it's almost inverting the paradigm.
The number is computable iff the TM says it is. Traditionally,
in order for the TM to say something about the number,
the number has to be the INPUT, NOT the output, of the TM.
TMs are normally thought of as running on their input in order to
answer a question about it.

 : Assume that each TM can be represented by a unique natural number.

That does not need to be assumed; that is inherent in the definition of "TM".

 : Since the number of TMs is countable, there must be a countable number of
 : comptable numbers.

Right.

Why isn't that just The Answer to the original question?
Why didn't knowing this in advance prevent you, in advance,
from asking the original question?

 : We need to define the output tapes more precisely.

Far more importantly, you need to define the INPUT tapes
precisely. The output tapes are potentially irrelevant.
The *important* output of a TM is whether it halts
or loops.

 : Each output tape is unbounded, but finite and every position
 : not written to by the TM is initially set to zero.

The input and output tapes of a TM (viewed as variables, not constants; viewed
as holes, not pegs) are, under the traditional definition, THE SAME (the
same holes; but they can start with some pegs and finish with others).
Since 0 is going to be inescapably needed as a true
data-value in almost anybody's representation of "numbers", You need to pick
some OTHER symbol as your default. Most TM alphabets come with a built-in
designated "null" symbol. When I was in college we spelled that as an upside-down
delta.

 : Define the ordered set S as the set of numbers defined by
 :
 : S(i) = output of TM(i).

TM(i) DOES NOT have a unique well-defined output!
What TM(i)'s output is will VARY depending on what TM(i)'s INPUT was!
Of course, you may, if you insist, make the input every bit as irrelevant
as the output by assuming that it is always null, but you will wind up
with a much bigger uglier collection of TM's to solve whatever problem
you were originally planning to solve.
 
 : Let d be the diagonal number.
 : To compute d(i) take the ith position of S(i):
 : If it is equal to 0 then d(i) = 1 else d(i) = 0.

It is going to dawn on you in a minute that since i
can take every natural number as a value, and there are infinitely
many of these, you have just defined a d with infinitely many digits.

 : Can d can be written to an unbounded, but finite output tape?
 : Probably not. The length of d is the largest i.

But there IS NO largest i, OBVIOUSLY.

 : Is the set of natural numbers a set of computable numbers?

Of course.
Every natural number is finite and every finite number
has the property that a TM can write it, once you decide on
a digital representation scheme. 

-- 
 ---
  "It's difficult ... you need to be united to have any 
   strength, but internal issues have to  be addressed."
 --- E. Ray Lewis, on  liberalism in America