Re: New countable infiniity logic

From: Paul Chapman (paul_at_igblan.free-online.co.uk)
Date: 10/22/04 

Date: Fri, 22 Oct 2004 01:34:42 +0100

"|-|erc" <spam@fodder.abc> wrote:

> As all the programmers here know, the infinite list of all computable
numbers UTM(n) neN
> produces all numbers with every combination of digits. You cannot defeat
infinity.

Careful. This (countable) list of computable numbers contains all numbers
with every FINITE "combination" (sequence of digits in the deminal
expansion) of digits, and all numers with every REPEATING infinite decimal
expansion, but only SOME numbers with a non-repeating infinite decimal
expansion.

> Say you have an *infinite* list of computable real numbers.

I assume by "an infinite list" you mean "an enumeration with cardinality
Aleph_0".

But you don't make clear whether or not you're considering a COMPLETE
enumeration of ALL of the computable numbers. This is important.

> Then Cantor comes along and shows an anti-diagonal.

If the enumeration is not complete, then there is no contradiction that the
diagonal is missing from the enumeration AND computable. The enumeration
never claimed that it was complete.

If the enumeration is complete, then the diagonal is, indeed, uncomputable.

To see this, try to COMPUTE a COMPLETE enumeration of the computable
numbers.

Let's be sure we know what we mean by this. Ignoring digits to the left of
the decimal point, such a "computation" would, for given i,j>=0, return the
ith digit of the decimal expansion of the jth number in the list. A second
program could then be written which called the above program with increasing
k, with i=j=k, to get the kth digit of the kth computable number, and then
alter it a la Cantor, to give the kth digit of a new number. And if all of
this were possible, then, yes, it would look as if we had a new computable
number not in the original enumeration, which would be a contradiction.

But it isn't possible to perform this computation, because of the halting
problem.

We can't build a TM (or program a UTM) which enumerates ALL of the
computable numbers, because we can only enumerate what's computable by
enumerating TMs. But some TMs don't halt, and furthermore we can't write a
general program to determine if an arbitrary TM will halt or not. Sooner or
later, as we enumerate the TMs in order to enumerate ALL computable numbers,
we will come to a TM which does not halt, and which our program cannot
establish is non-halting. Thus our program will stall at this TM, and run
forever trying in vain to calculate the kth digit of the computable number
we're hoping it embodies.

Now, if you can come up with a TM which computes a list of ALL computable
numbers WITHOUT needing to enumerate TMS, then we will all have to think
again. :)

Cheers, Paul

Relevant Pages

  • Re: New countable infiniity logic
    ... > produces all numbers with every combination of digits. ... and all numers with every REPEATING infinite decimal ... I assume by "an infinite list" you mean "an enumeration with cardinality ... enumerating TMs. ...
    (sci.logic)
  • Re: abundance of irrationals!)
    ... And digits of what? ... Infinite strings ... when I referred to correspondence between the nodes of a binary tree ... it's still an enumeration of the reals. ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... >>> n significant digits. ... By normal tree traversal, an infinite binary ... >>> Cantor's diagonal proof which cimple proves there are more reals than ... >> in your enumeration. ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... >>> in your enumeration. ... >> This was supposed to be an infinite binary tree, ... >> infinite digits. ... >>> the reals in your enumeration. ...
    (sci.math)
  • Re: Question regarding the diagonal method.
    ... denumerable binary strings, a string 111... ... the enumeration. ... Then define Sby looking at blocks of three digits at a time; ...
    (sci.logic)
Loading