Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 Virgil Posts: 8,833 Registered: 1/6/11
Re: Matheology � 257
Posted: Apr 22, 2013 2:51 PM

In article
WM <mueckenh@rz.fh-augsburg.de> 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
--

Date Subject Author
4/22/13 mueckenh@rz.fh-augsburg.de
4/22/13 fom
4/22/13 David Petry
4/22/13 fom
4/23/13 mueckenh@rz.fh-augsburg.de
4/23/13 Virgil
4/23/13 Charlie-Boo
4/23/13 fom
4/22/13 Scott Berg
4/22/13 Virgil
4/22/13 Virgil
4/23/13 Charlie-Boo