Re: Problem demonstrating that the set of binary strings is uncountable.

From: Poker Joker (Poker_at_wi.rr.com)
Date: 08/13/04 

Date: Fri, 13 Aug 2004 16:35:42 GMT

"Dave Seaman" <dseaman@no.such.host> wrote in message
news:cfip7m$3es$1@mozo.cc.purdue.edu...
> On Fri, 13 Aug 2004 15:04:00 GMT, Poker Joker wrote:
> > "Dave Seaman" <dseaman@no.such.host> wrote in message
> > news:cfijvj$19k$1@mozo.cc.purdue.edu...
> >> On Fri, 13 Aug 2004 13:53:21 GMT, Poker Joker wrote:
>
> ><snip>
>
> >> > The issue is:
> >> > Cantor's proof describes an algorithm. Right or wrong?
> >>
> >> What do you mean by an algorithm? Cantor's proof does not describe
> > anything
> >> that can be carried out by a Turing machine. I have already explained
> > why.
>
> > Given a list of reals, why can't a Turing machine can generate the
"real"
> > from the digits
> > along the diagonal as described by Cantor. You explained something that
> > needs no
> > explanation: Uncountability.
>
> I have explained why. There are two subtasks that need to be carried
> out, and neither can be implemented by a TM, in general:
>
> 1. Find the n'th number in the list.
> 2. Find the n'th digit of that number.
>
> Step 1 can be carried out only if the given list is recursively
> enumerable, and you have already admitted that not every list of real
> numbers is recursively enumerable.

Why can't a TM find the n'th number in a given list?
Cantor's proof begins with the assumption that the list is
given. Are you saying Cantor proved that reals aren't
recursively enumerable via an argument that begins with
the assumption that no list of reals is recursively enumerable?

The proof is essentially:

1. Assume a list of reals.
2. Construct (COMPUTE!) a real via the digits along
  the diagonal.
3. Show the constructed (COMPUTED!) real must not
  be included in the list.
4. Conclude no list could be complete.

> Step 2 can be carried out only if the n'th number in the list is a
> computable real. Not all reals are computable. Do you agree?

I agree that the proof may have problems because the given list
may have uncomputable reals. If the diagonal number is an
uncomputable real, then the explicitly given construction, which
just happens to be an algorithm for computing real numbers,
is not sufficient. The construction must be shown to be possible
without it being an algorithm *OR* uncomputable reals must not
be so "uncomputable." We can't have it both ways. You can
say that the number just needs to be "shown to exist" somehow,
but "showing the existance" is not consistant with computability
theory. Something seems to be wrong.

Relevant Pages

  • Re: Error in Turings paper On computable numbers, with an application to th..
    ... Bishop doesn't describe the sequence numerically; ... but I assume he means that there's a Turing machine ... that when given an index of a Turing machine computing x, ... If the reals are all given as binary expansions, ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... sequence of reals. ... a rational approximation to fto within 1/n as follows. ... gives us a way of computing modulus of uniform continuity ...
    (sci.logic)
  • Re: etc
    ... to integer constraints) process that would allow the construction, ... between the two subsets of the reals - you can't specify a computational ... An algorithm for generating the successive digits of e.g. pi, ... Coin tossing is computing a number. ...
    (sci.math)
  • Re: functions that halt
    ... number of reals that we can't even describe, ... all the proofs of uncomputability I can think of prove ... programme with Gödel number n halts is not computable. ... nothing to specify the reason behind computing B; ...
    (comp.theory)
  • Re: Cantor Confusion
    ... there is no list of all reals. ... given by a Turing machine. ... Computing ... any sequence of decimal numbers is *by the very ...
    (sci.math)