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: 8,833
Registered: 1/6/11
Re: Matheology � 257
Posted: Apr 22, 2013 2:51 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

In article
WM <> wrote:

> 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

But WM has just described an algorithm for computing it.

Besides which, there may well be, at least as far as WM knows, some
other algorithm which generates the same sequence of 3's an 4's

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.