From ownercse584sp07list@LISTSERV.BUFFALO.EDU Tue Mar 20 11:29:50 2007
Received: from ares.cse.buffalo.edu (ares.cse.Buffalo.EDU [128.205.32.79])
by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l2KFTorv020949
for ; Tue, 20 Mar 2007 11:29:50 0400 (EDT)
Received: from front1.acsu.buffalo.edu (upfront.acsu.buffalo.edu [128.205.4.140])
by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2KFTesG050592
for ; Tue, 20 Mar 2007 11:29:40 0400 (EDT)
Received: (qmail 394 invoked from network); 20 Mar 2007 15:29:39 0000
Received: from mailscan7.acsu.buffalo.edu (128.205.6.158)
by front1.acsu.buffalo.edu with SMTP; 20 Mar 2007 15:29:39 0000
Received: (qmail 868 invoked from network); 20 Mar 2007 15:29:38 0000
Received: from deliverance.acsu.buffalo.edu (128.205.7.57)
by front3.acsu.buffalo.edu with SMTP; 20 Mar 2007 15:29:38 0000
Received: (qmail 20759 invoked from network); 20 Mar 2007 15:29:31 0000
Received: from listserv.buffalo.edu (128.205.7.35)
by deliverance.acsu.buffalo.edu with SMTP; 20 Mar 2007 15:29:31 0000
Received: by LISTSERV.BUFFALO.EDU (LISTSERVTCP/IP release 14.5) with spool id
3953941 for CSE584SP07LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007
11:29:31 0400
DeliveredTo: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
Received: (qmail 10620 invoked from network); 20 Mar 2007 15:29:30 0000
Received: from mailscan1.acsu.buffalo.edu (128.205.6.133) by
listserv.buffalo.edu with SMTP; 20 Mar 2007 15:29:30 0000
Received: (qmail 3768 invoked by uid 60001); 20 Mar 2007 15:29:25 0000
XMailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.11
MIMEVersion: 1.0
ContentType: text/plain; charset=Big5HKSCS
ContentTransferEncoding: 8bit
XOriginatingIP: 72.88.52.205
XUBRelay: (internal)
XPMELSpamProb: X: 18%
MessageID: <1174404565.45fffdd56ec67@mail1.buffalo.edu>
Date: Tue, 20 Mar 2007 11:29:25 0400
ReplyTo: nhj@BUFFALO.EDU
Sender: "Philosophy of Computer Science, Spring 2007"
From: Nicolas Jackson
Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND!
To: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
Precedence: list
ListHelp: ,
ListUnsubscribe:
ListSubscribe:
ListOwner:
ListArchive:
XUBRelay: (deliverance.acsu.buffalo.edu)
XDCCBuffalo.EDUMetrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0
XSpamStatus: No, score=1.3 required=5.0 tests=AWL,BAYES_00,
MANY_EXCLAMATIONS,SUBJ_ALL_CAPS autolearn=no version=3.1.7
XSpamCheckerVersion: SpamAssassin 3.1.7 (20061005) on
ares.cse.buffalo.edu
XVirusScanned: ClamAV 0.88.6/2880/Tue Mar 20 01:04:21 2007 on ares.cse.buffalo.edu
XVirusStatus: Clean
Status: R
ContentLength: 3597
I used to think I understood Cantor's diagonalization proof for the
uncountability of the reals, but now I'm not so sure. Specifically, I am
not convinced that diagonalizing over an infinite set is valid. I know
Godel, Cantor, and Turing knew what they were doing, so I'd apretiate it
if anyone could tell me where I'm going wrong.
It seems to me that it is possible to make a diagonalization argument
with all true premises and a false conclusion (so diagonalization is
invalid). Specifiacally I don't see why Cantor's diagonal argument for
the uncountability of the reals can't be used to demonstate that the
countable numbers are uncountable by just "flipping" the digits over the
decimal point. I'll use Chaitin's phrasing of the argument to demonstrate:
Suppose we have a list of all the countable numbers. Let d(i,j) be the
jth digit of the ith number in the list. Let our representation of each
countable number be preceeded by an infinite number of 0's so that the
function is N^2>{0,1,2,3,4,5,6,7,8,9}. So if our list is 1, 2, 3, 4, 5,
etc. (the most obvious ordering of the countable numbers) d(1,1)=1,
d(563,2)=6, d(1,2)=0, and d(1,x)=0 for all x>1.
Consider the countable number n whose kth digit is defined as 4 if
d(k,k)=3 and 3 otherwise. In other words, we form n by taking all the
digits on the diagonal of the list of all reals, and then changing each
of these diagonal digits. (Note that the diagonal in this argument goes
from the top right of the matrix to the bottom left instead of from the
top left to the bottom right, though this is trivial (I think) since we
could just redifine d or n to use the other diagonal. I did it this way
because I think it is simpler and clearer.)
The countable number n differs from the ith real in this presumably
complete list of all countable numbers because their ith digits are
different. Therefore this list cannot be complete, and the set of
countable numbers is uncountable. Q.E.D. This is, obvoiusly, a problem.
The reason why diagonalization is invalid seems to me to be that one
cannot actually construct the infinitely long real r (or countable
number n) in a finite amount of time. At any time t (lets say that it
takes one unit of time to find one digit of r or n) we have a real r (or
a countable number n) that is not in the ordering of reals (or countable
numbers) numbered 1 to t, but absolutely is in the interval of reals (or
countable numbers) from t off to infinity.
I apologize for writing such a long email. I tried to make it as brief
as possible while still making a complete thought on the issue. Anything
shorter would just lead to confussion. I hope someone will take the time
to read this and set me straight (or, I guess, diagonal ;).
Nicolas Jackson
Quoting "William J. Rapaport" :

>  >
>  > In class today, we discussed the similarities of the argument
> that an
>  > interaction machine can be simulated by a finite number of TMs to
> the
>  > argument that there are an infinite number of real numbers, hence
> that
>  > there are unnameable reals.
>  >
>  > If you're interested in following up on some of these ideas,
> here's an
>  > interesting and even readable(!) paper by a wellknown
> theoretician of
>  > computation:
>  >
>  > Chaitin, Gregory (2006),
>  > "How Real Are Real Numbers?",
>  > International Journal of Bifurcation and Chaos
>  >
>  > PDF: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/olympia.pdf
>  > html: http://tinyurl.com/2eh7tj
>  >
> 
>
>
>
From ownercse584sp07list@LISTSERV.BUFFALO.EDU Tue Mar 20 13:58:44 2007
Date: Tue, 20 Mar 2007 13:58:16 0400
From: Albert Goldfain
Subject: Re: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND!
To: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
Interesting post Nick! In general, there are some very deep issues with
real numbers in mathematics and it is not surprising that these come out
in the diagonalization argument.
Not to disregard the bulk of your email, but here's what I believe to be
the crux of your complaint:
> The reason why diagonalization is invalid seems to me to be that one
> cannot actually construct the infinitely long real r (or countable
> number n) in a finite amount of time. At any time t (lets say that it
> takes one unit of time to find one digit of r or n) we have a real r (or
> a countable number n) that is not in the ordering of reals (or countable
> numbers) numbered 1 to t, but absolutely is in the interval of reals (or
> countable numbers) from t off to infinity.
And here's my two cents:
The real r is constructed stepbystep by switching the diagonal digit in
the (allegedly exhaustive) list of reals. I believe what it means to say
that a real number is "constructable" is simply that we know at each step
how to "construct" the next digit of the number even if we don't have time
to finish such a construction (Do you mean something very different in
your use of "construction" than "computation"?). Under this
characterization r is constructable.
However, there are several issues regarding the validity of arguments that
refer to arbitrary reals. One of the problems is how to refer to the
reals we don't have names for (or may be unnameable). I recently read
the following paper (see attached) which you may find useful:
Martino, Enrico (2001), "Arbitrary Reference in Mathematical Reasoning",
Topoi 20: 6577.
The reals are partitioned into the rationals and irrationals. Each
rational can be expressed as an integer divided by a nonzero integer.
Any integer can be "named" in a finite time and, thus, so can any
rational (although this time might be quite large).
*SOME* irrationals can be referred to in a finite time. For example:
"pi is the ratio of the circumference of any circle to its diameter."
Clearly this utterance refers to pi in a finite time, but can it "name" pi
without printing out its digits? Perhaps you are willing to allow some
irrationals to be named by reference?

I think a lot of people are disregarding the Accelerating Turing
Machine as a logical (yet perhaps physically impossible) way of dealing
with the infinite length of numbers like pi and the diagonalized r.
So here is an attempt to mutate the accelerating TM into Zeno's paradox
(buckle up :)):
Try to poke a hole in this argument:
P1. I want to write the digits of pi and I have an algorithm for precisely
computing the next digit of pi from previous digits (such algorithms *do*
exist).
P2. I can start in the middle of a room and write the number 3 and '.' on
the floor.
P3. I can walk halfway towards the wall and write the number 1 on the
floor.
P4. I can walk halfway towards the wall and write the number 4 on the
floor.
P5. I can keep walking halfway towards the wall and writing the next
number of pi on the floor.
P6. I will have written pi once I reach the wall.
P7. I can reach the wall by walking from the center of the room to the
wall (I have done this before :)).
C. Thus I can write down all of the digits of pi.
There are some space problems with P5 and an even bigger issue of whether
I can reach the wall if I augment my walking procedure with this
stopandwriteadigit step. So now consider the following (better)
argument:
P1. I want to THINK of each digit of pi and I have MEMORIZED an algorithm
for precisely computing the next digit of pi from previous digits (such
algorithms *do* exist).
P2. I can start in the middle of a room and think of the number 3 and a
'.'.
P3. I can walk halfway towards the wall and think of the number 1.
P4. I can walk halfway towards the wall and think of the number 4.
P5. I can keep walking halfway towards the wall and thinking of the
next digit of pi.
P6. I will have thought of all the digits of pi once I reach the wall.
P7. I can reach the wall by walking from the center of the room to the
wall (I have done this before :)).
C. Thus I can think of all of the digits of pi.
Now since my motion to the wall *is* possible, this would require my
thought to accelerate as I think of the digits...however, without seeing the
contents of my brain, how do you know I am not thinking of all of the
digits of pi each time I walk to a wall? :) [suppose also that I can
forget as many previous digits as necessary to attend to the current one I
am computing].
I guess I answered with a pretty long post myself...sorry...but
some interesting stuff to think about.
Albert
From ownercse584sp07list@LISTSERV.BUFFALO.EDU Tue Mar 20 16:02:53 2007
Received: from ares.cse.buffalo.edu (ares.cse.Buffalo.EDU [128.205.32.79])
by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l2KK2rT8003307
for ; Tue, 20 Mar 2007 16:02:53 0400 (EDT)
Received: from front3.acsu.buffalo.edu (coldfront.acsu.buffalo.edu [128.205.6.89])
by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2KK2iMc070641
for ; Tue, 20 Mar 2007 16:02:44 0400 (EDT)
Received: (qmail 10204 invoked from network); 20 Mar 2007 20:02:44 0000
Received: from mailscan3.acsu.buffalo.edu (128.205.6.135)
by front3.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:44 0000
Received: (qmail 5869 invoked from network); 20 Mar 2007 20:02:41 0000
Received: from deliverance.acsu.buffalo.edu (128.205.7.57)
by front1.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:41 0000
Received: (qmail 16977 invoked from network); 20 Mar 2007 20:02:22 0000
Received: from listserv.buffalo.edu (128.205.7.35)
by deliverance.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:22 0000
Received: by LISTSERV.BUFFALO.EDU (LISTSERVTCP/IP release 14.5) with spool id
3968059 for CSE584SP07LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007
16:02:22 0400
DeliveredTo: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
Received: (qmail 16598 invoked from network); 20 Mar 2007 20:02:21 0000
Received: from mailscan6.acsu.buffalo.edu (128.205.7.95) by
listserv.buffalo.edu with SMTP; 20 Mar 2007 20:02:21 0000
Received: (qmail 821 invoked by uid 60001); 20 Mar 2007 20:02:17 0000
References: <1174404565.45fffdd56ec67@mail1.buffalo.edu>
XMailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.11
MIMEVersion: 1.0
ContentType: text/plain; charset=Big5HKSCS
ContentTransferEncoding: 8bit
XOriginatingIP: 72.88.52.205
XUBRelay: (internal)
XPMELSpamProb: X: 18%
MessageID: <1174420937.46003dc994ed2@mail1.buffalo.edu>
Date: Tue, 20 Mar 2007 16:02:17 0400
ReplyTo: nhj@BUFFALO.EDU
Sender: "Philosophy of Computer Science, Spring 2007"
From: Nicolas Jackson
Subject: Re: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND!
Comments: To: Albert Goldfain
To: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
InReplyTo:
Precedence: list
ListHelp: ,
ListUnsubscribe:
ListSubscribe:
ListOwner:
ListArchive:
XUBRelay: (deliverance.acsu.buffalo.edu)
XDCCBuffalo.EDUMetrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0
XSpamStatus: No, score=1.8 required=5.0 tests=AWL,BAYES_00,
MANY_EXCLAMATIONS autolearn=unavailable version=3.1.7
XSpamCheckerVersion: SpamAssassin 3.1.7 (20061005) on
ares.cse.buffalo.edu
XVirusScanned: ClamAV 0.88.6/2880/Tue Mar 20 01:04:21 2007 on ares.cse.buffalo.edu
XVirusStatus: Clean
Status: R
ContentLength: 3229
Thanks for the reply Albert. It's helping flush out exactly what my
objections are.
Albert said:
>I believe what it means to say that a real number is
>"constructable" is simply that we know at each step
>how to "construct" the next digit of the number even
>if we don't have time to finish such a construction
That is how I understand "constructable" and "computable" to be defined
in the literature and in class. My objection is that in the case of
constructing the real r it is not that we don't have time to finish the
number but that there is no such thing as enough time to finish it.
What's more, I am not sure I believe such an r exists since at any time
k r is different than all reals preceding k, but there is no compelling
reason to believe that r is not in the infinite number of reals
succeeding k.
Another problem I have is that if you allow for constructions that take
an infinite amount of time it seems that one can construct a list of all
reals. Is this naming them since it is just a list of all of them and it
cannot really be used (until after it is constructed, i.e. infinite time
from now) to identify a particular one? The algorithm is as follows.
1.Write a decimal point
2.For(i=1;i; Tue, 20 Mar 2007 16:02:53 0400 (EDT)
Received: from front3.acsu.buffalo.edu (coldfront.acsu.buffalo.edu [128.205.6.89])
by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2KK2iMc070641
for ; Tue, 20 Mar 2007 16:02:44 0400 (EDT)
Received: (qmail 10204 invoked from network); 20 Mar 2007 20:02:44 0000
Received: from mailscan3.acsu.buffalo.edu (128.205.6.135)
by front3.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:44 0000
Received: (qmail 5869 invoked from network); 20 Mar 2007 20:02:41 0000
Received: from deliverance.acsu.buffalo.edu (128.205.7.57)
by front1.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:41 0000
Received: (qmail 16977 invoked from network); 20 Mar 2007 20:02:22 0000
Received: from listserv.buffalo.edu (128.205.7.35)
by deliverance.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:22 0000
Received: by LISTSERV.BUFFALO.EDU (LISTSERVTCP/IP release 14.5) with spool id
3968059 for CSE584SP07LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007
16:02:22 0400
DeliveredTo: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
Received: (qmail 16598 invoked from network); 20 Mar 2007 20:02:21 0000
Received: from mailscan6.acsu.buffalo.edu (128.205.7.95) by
listserv.buffalo.edu with SMTP; 20 Mar 2007 20:02:21 0000
Received: (qmail 821 invoked by uid 60001); 20 Mar 2007 20:02:17 0000
References: <1174404565.45fffdd56ec67@mail1.buffalo.edu>
XMailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.11
MIMEVersion: 1.0
ContentType: text/plain; charset=Big5HKSCS
ContentTransferEncoding: 8bit
XOriginatingIP: 72.88.52.205
XUBRelay: (internal)
XPMELSpamProb: X: 18%
MessageID: <1174420937.46003dc994ed2@mail1.buffalo.edu>
Date: Tue, 20 Mar 2007 16:02:17 0400
ReplyTo: nhj@BUFFALO.EDU
Sender: "Philosophy of Computer Science, Spring 2007"
From: Nicolas Jackson
Subject: Re: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND!
Comments: To: Albert Goldfain
To: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
InReplyTo:
Precedence: list
ListHelp: ,
ListUnsubscribe:
ListSubscribe:
ListOwner:
ListArchive:
XUBRelay: (deliverance.acsu.buffalo.edu)
XDCCBuffalo.EDUMetrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0
XSpamStatus: No, score=1.8 required=5.0 tests=AWL,BAYES_00,
MANY_EXCLAMATIONS autolearn=unavailable version=3.1.7
XSpamCheckerVersion: SpamAssassin 3.1.7 (20061005) on
ares.cse.buffalo.edu
XVirusScanned: ClamAV 0.88.6/2880/Tue Mar 20 01:04:21 2007 on ares.cse.buffalo.edu
XVirusStatus: Clean
Status: RO
ContentLength: 3229
Thanks for the reply Albert. It's helping flush out exactly what my
objections are.
Albert said:
>I believe what it means to say that a real number is
>"constructable" is simply that we know at each step
>how to "construct" the next digit of the number even
>if we don't have time to finish such a construction
That is how I understand "constructable" and "computable" to be defined
in the literature and in class. My objection is that in the case of
constructing the real r it is not that we don't have time to finish the
number but that there is no such thing as enough time to finish it.
What's more, I am not sure I believe such an r exists since at any time
k r is different than all reals preceding k, but there is no compelling
reason to believe that r is not in the infinite number of reals
succeeding k.
Another problem I have is that if you allow for constructions that take
an infinite amount of time it seems that one can construct a list of all
reals. Is this naming them since it is just a list of all of them and it
cannot really be used (until after it is constructed, i.e. infinite time
from now) to identify a particular one? The algorithm is as follows.
1.Write a decimal point
2.For(i=1;i; Tue, 20 Mar 2007 20:03:48 0400 (EDT)
Received: from front3.acsu.buffalo.edu (coldfront.acsu.buffalo.edu [128.205.6.89])
by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2L03Gll085373
for ; Tue, 20 Mar 2007 20:03:16 0400 (EDT)
Received: (qmail 27772 invoked from network); 21 Mar 2007 00:03:16 0000
Received: from mailscan8.acsu.buffalo.edu (128.205.7.55)
by front3.acsu.buffalo.edu with SMTP; 21 Mar 2007 00:03:16 0000
Received: (qmail 11644 invoked from network); 21 Mar 2007 00:03:15 0000
Received: from deliverance.acsu.buffalo.edu (128.205.7.57)
by front2.acsu.buffalo.edu with SMTP; 21 Mar 2007 00:03:15 0000
Received: (qmail 26814 invoked from network); 21 Mar 2007 00:03:13 0000
Received: from listserv.buffalo.edu (128.205.7.35)
by deliverance.acsu.buffalo.edu with SMTP; 21 Mar 2007 00:03:13 0000
Received: by LISTSERV.BUFFALO.EDU (LISTSERVTCP/IP release 14.5) with spool id
3975768 for CSE584SP07LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007
20:03:13 0400
DeliveredTo: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
Received: (qmail 14753 invoked from network); 21 Mar 2007 00:03:13 0000
Received: from mailscan6.acsu.buffalo.edu (128.205.7.95) by
listserv.buffalo.edu with SMTP; 21 Mar 2007 00:03:13 0000
Received: (qmail 7716 invoked from network); 21 Mar 2007 00:03:12 0000
Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp3.acsu.buffalo.edu
with SMTP; 21 Mar 2007 00:03:12 0000
Received: from castor.cse.Buffalo.EDU (rapaport@localhost [127.0.0.1]) by
castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l2L03CXC012174
for ; Tue, 20 Mar 2007
20:03:12 0400 (EDT)
Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU
(8.13.6/8.12.9/Submit) id l2L03CQ9012173 for
CSE584SP07LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007 20:03:12
0400 (EDT)
XUBRelay: (castor.cse.buffalo.edu)
XPMELSpamProb: : 7%
MessageID: <200703210003.l2L03CQ9012173@castor.cse.Buffalo.EDU>
Date: Tue, 20 Mar 2007 20:03:12 0400
ReplyTo: "William J. Rapaport"
Sender: "Philosophy of Computer Science, Spring 2007"
From: "William J. Rapaport"
Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND!
To: CSE584SP07LIST@LISTSERV.BUFFALO.EDU
Precedence: list
ListHelp: ,
ListUnsubscribe:
ListSubscribe:
ListOwner:
ListArchive:
XUBRelay: (castor.cse.buffalo.edu)
XDCCBuffalo.EDUMetrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0
XSpamStatus: No, score=1.6 required=5.0 tests=AWL,BAYES_00,
MANY_EXCLAMATIONS,SUBJ_ALL_CAPS autolearn=no version=3.1.7
XSpamCheckerVersion: SpamAssassin 3.1.7 (20061005) on
ares.cse.buffalo.edu
XVirusScanned: ClamAV 0.88.6/2883/Tue Mar 20 18:49:34 2007 on ares.cse.buffalo.edu
XVirusStatus: Clean
Status: RO
ContentLength: 4575
Nicolas wrote:
 Date: Tue, 20 Mar 2007 11:29:25 0400
 From: Nicolas Jackson
 Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND!

 ...
 Suppose we have a list of all the countable numbers.
Here's my first problem. What do you mean by a "countable" number?
>From the rest of your posting, it seems as if you mean "natural" number;
is that right? (There's no such thing as a "countable" number. There
are the naturals: 1, 2, 3, ...
the nonnegative integers: 0, 1, 2, 3, ...
the integers: ... 3, 2, 1, 0, 1, 2, ...
the rationals, the reals, the complex.
A set of numbers is countable iff it can be put into 11 correspondence
with the naturals, i.e, iff it can be counted.
 Let d(i,j) be the
 jth digit of the ith number in the list. Let our representation of each
 countable number be preceeded by an infinite number of 0's so that the
 function is N^2>{0,1,2,3,4,5,6,7,8,9}. So if our list is 1, 2, 3, 4, 5,
 etc. (the most obvious ordering of the countable numbers) d(1,1)=1,
 d(563,2)=6, d(1,2)=0, and d(1,x)=0 for all x>1.
Another problem or two: You say that d(1,2)=0, i.e., that the 2nd digit
of the first number on the list is 0. The first number on your list is
1; it has no second digit. So your definition of d is not clear to me.
Moreover, if my interpretation is correct, then note that
d(1,2)=d(10,2); I don't know if that's important or not. But you also
say that you want each number to be preceeded by an infinite string of
0s. In that case, how do you manage to talk about the "first" digit?
 Consider the countable number n whose kth digit is defined as 4 if
 d(k,k)=3 and 3 otherwise. In other words, we form n by taking all the
 digits on the diagonal of the list of all reals, and then changing each
 of these diagonal digits.
If we just use the natural numbers in their standard ordering:
1
2
3
...
10
11
...
13848759
...
and interpret your d function as I have interpreted it above, then
n=33333333.... (maybe with an occasional 4 somewhere in there, but
I doubt it). But note that either n is not a natural number, because
it'll have an infinite number of digits, so it wouldn't be on the list
anyway, or else n is finite, in which case we know that it's on the
list (by the way the list was defined).
 (Note that the diagonal in this argument goes
 from the top right of the matrix to the bottom left instead of from the
 top left to the bottom right, though this is trivial (I think) since we
 could just redifine d or n to use the other diagonal. I did it this way
 because I think it is simpler and clearer.)
I'm afraid I don't understand this. Or are you thinking of the list
as rightjustified, like this:
1
2
...
10
11
...
398475
...
I don't see how this changes things.
 The countable number n differs from the ith real in this presumably
 complete list of all countable numbers because their ith digits are
 different. Therefore this list cannot be complete, and the set of
 countable numbers is uncountable. Q.E.D. This is, obvoiusly, a problem.
Nodon't forget that unlike Cantor's diagonal argument, each number
on your list is finite. So when n is created, it will match some number
on the list IF it's finite (and if it isn't, then we already knew it
wasn't on the list, because it can't be a natural number).
 The reason why diagonalization is invalid seems to me to be that one
 cannot actually construct the infinitely long real r (or countable
 number n) in a finite amount of time.
Ah, but that's bringing into mathematics the limitations of time and
space, which are not normally brought in. Real, physical systems might
be subject to these limitations, but math isn't. At least, classical
math isn't. There is, however, a kind of math called "intuitionistic"
math that only recognizes mathematical entities that can be thought of
by humans, hence that have some spatiotemporal limitations. To find
out more about this kind of math (which, by the way, doesn't allow you
do to calculus!), take a look at:
Benacerraf, Paul; & Putnam, Hilary (yesthat Hilary Putnam, the one
who thinks that anything can
implement an FSA)
(1964),
Philosophy of Mathematics: Selected Readings
(Englewood Cliffs, NJ: Prentice Hall).
You're not alone in your doubts about these infinite methods,
but I don't think that your argument above is clear enough
to challenge them (yet).