Re: Cardinality of Set of Computable Numbers?

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

Date: Fri, 26 Dec 2003 08:16:55 -0800

In article <lpmdnYv-KIWGNXaiRVn-hQ@comcast.com>, Russell Easterly
<logiclab@comcast.net> wrote:

> "Chan-Ho Suh" <suh@math.ucdavis.nospam.edu> wrote in message
> news:251220031650055558%suh@math.ucdavis.nospam.edu...
> > 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?
>
> Good question. I need to define what computable means.
>
> > In other words, you need a finite rule to compute this d. I don't
> > think you're going to find one.
>
> Maybe not.
> Let a computable number be defined as the unbounded, but finite output tape
> of a TM. Assume that each TM can be represented by a unique natural number.
>
> Since the number of TMs is countable, there must be a countable number of
> comptable numbers.
>

Your conclusion is right, but your definition of computable needs work.
See below.

> We need to define the output tapes more precisely.
> Each output tape is unbounded, but finite and every position
> not written to by the TM is initially set to zero.
>

Here's the way Turing did it: every square on the tape is initially
blank. The TM outputs 0s and 1s (and possibly other symbols, which we
regard as 'garbage'). Any number between zero and one is called
computable if there's a TM that starts with a blank tape and produces
the binary expansion of the number (disregarding any garbage produced).
This binary expansion is culled from the subsequence of the sequence of
moves that produces 0s and 1s, so the 0s and 1s don't need to be
printed out in the right order on the tape and actually the TM may
overwrite some of the previously produced 0s and 1s.

In general a computable number is one that differs by an integer from
such a computable number between one and zero.

Important point: a number with terminating binary expansion may be
computed by a TM that *does NOT halt*.

> Define the ordered set S as the set of numbers defined by
>
> S(i) = output of TM(i).
>
> 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.
>
> Can d can be written to an unbounded, but finite output tape?
> Probably not. The length of d is the largest i.
>

Hmm...I'm not getting what you're saying. 'i' seems to be the way you
are indexing the TMs. So what do you mean by largest 'i'? Of course,
d is likely to be some irrational number and have infinite length, but
that's not why it's not computable.

The point is that a TM that computes d, according to your scheme, must
first output S(i) to enough digits -- the i'th digit to be precise, in
order to figure out the i'th digit of d-- or *halt* after a certain
point before reaching the i'th digit so that you know the rest of the
digits are zero. So picture this: your TM starts computing S(i), but
maybe it takes a long time to get to the i'th digit; in any case you
get it eventually. But the TM may chug on, i.e. it is a non-halting
TM! Now of course, since this TM is really like a "sub"-TM of the one
that computes d, you may say you'll just arrange it so that as part of
the computing of d, you figure out if TM(i) halts or not. Well, now
you (hopefully) see the difficulty involved.

Actually, I dug out Turing's paper on computable numbers since my
curiosity was piqued, and I'm struck by how readable it still seems.
In fact, your very question is addressed! Since it seems you are not
operating with a text, I suggest getting a copy of the paper; it's not
only clear but has some of the most fundamental concepts of TMs in a
fairly short form. It should be available at your university library.

A.M. Turing, "On Computable Numbers, with an Application to the
Entscheidungsproblem.", Proceedings of the London Mathematical Society,
vol 42 (1936) p. 230-265.

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

Yes. I can compute them pretty easily ;-)

Just remember that Turing's definition of computable number is a fairly
natural one. It includes basically everything you would think of as
'computable' and even probably some more.

> It seems computability implies countability,
> but countability does not imply computability.
>
>

I'm not sure what you're saying here. Of course we can always take a
countable set of uncomputable numbers.

> Russell
> - Merry Xmas
>
>

Happy Holidays.

Relevant Pages