The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Matheology § 257
Replies: 11   Last Post: Apr 23, 2013 5:05 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 1,635
Registered: 2/27/06
Re: Matheology § 257
Posted: Apr 23, 2013 10:37 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Apr 22, 3:03 am, WM <> wrote:
> Matheology § 257
> The set of all possible computer programs is countable {{if going into
> concrete details of computers, we can even say more restrictively: The
> number of all possible programs is finite and certainly less than
> 2^10^100. But of course Turing did not refer to real computers and did
> not know anything about the memory space of  an exploitable
> surronding. Therefore let us analyze his approach here.}}, therefore
> the set of all computable reals is countable, and diagonalizing over
> the computable reals immediately yields an uncomputable real. Q.E.D.
> {{Well, it is not always that easy to diagonalize over finite
> sequences. The following list has no diagonal:
> 0
> 1
> So we must take some more care, as will be done in the following.}}
>    Let's do it again more carefully.
>    Make a list of all possible computer programs. Order the programs
> by their size, and within those of the same size, order them
> alphabetically. The easiest thing to do is to include all the possible
> character strings that can be formed from the finite alphabet of the
> programming language, even though most of these will be syntactically
> invalid programs.
>    Here's how we define the uncomputable diagonal number 0 < r < 1.
> Consider the kth program in our list. If it is syntactically invalid,
> or if the kth program never outputs a kth digit, or if the kth digit
> output by the kth program isn't a 3, pick 3 as the kth digit of r.
> Otherwise, if the kth digit output by the kth program is a 3, pick 4
> as the kth digit of r.
>    This r cannot be computable, because its kth digit is different
> from the kth digit of the real number that is computed by the kth
> program, if there is one. Therefore there are uncomputable reals, real
> numbers that cannot be calculated digit by digit by any computer
> program. [...]
>    In other words, the probability of a real's being computable is
> zero, and the probability that it's uncomputable is one. [Who should
> be credited for this measure-theoretic proof that there are
> uncomputable reals? I have no idea. It seems to have always been part
> of my mental baggage.]
> [Gregory Chaitin: "How real are real numbers?" (2004)]
> The error occurs always at the same plase - that is common to all
> "uncountability-proofs". The completed infinite number of all finite
> programs is presupposed. Otherwise the just defined number would be
> generated by another finite process with a finite program. But the set
> of all finite things is not a completed infinity, it is potentially
> infinite. After all you cannot use a program that is longer than the
> longest program that is used. Nevertheless, up to every length, only a
> non-measurably small share of all usable finite programs has bee used.
> Regards, WM

BTW Turing handled the problem of finite memory by assuming you invest
a lump sum of money in a profitable business that supplies paper as
dividends at a faster rate than your computer uses it up!


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.