Le 19-mai-06, à 23:46, George Levy a écrit :

Bruno Marchal wrote:

Now I think I should train you with diagonalization. I give you an

exercise: write a program which, if executed, will stop on the biggest

possible natural number. Fairy tale version: you meet a fairy who

propose you a wish. You ask to be immortal but the fairy replies that

she has only finite power. So she can make you living as long as you

wish, but she asks precisely how long. It is up too you to describe

precisely how long you want to live by writing a program naming that

big (but finite) number. You have a limited amount of paper to write

your answer, but the fairy is kind enough to give you a little more if

you ask.

You can ask the question to very little children. The cutest answer I

got was "7 + 7 + 7 + 7 + 7" (by a six year old). Why seven? It was the

age of his elder brother!

Hint: try to generate an infinite set S of more and more growing and

(computable) functions, and then try to diagonalize it. S can be

{addition, multiplication, exponentiation, .... (?)....}. More hints

and answers later. I let you think a little bit before. (Alas it looks

I will be more busy in may than I thought because my (math) students

want supplementary lessons this year ...).

Any potentially largest finite number n that I could name could be incremented by 1 so this finite number could not be the largest. The trick is not to name a particular number but to specify a method to reach the unreachable.

Well, if *you* try to give the biggest natural number, *you* will never stop, and you will not succeed in specifying a large number, and the fairy will not make your wish coming true, and you will gain nothing. It would be absurd not saying 10^100 under the pretext that you would have prefer to live "(10^100)+1" years.

By trying to reach the unreachable, well, you are anticipating another fairy which I will present to you once you will be able to diagonalize without even thinking ...

Method 1) Use the fairy power against her.

I see you like to live dangerously. Or to die dangerously should I say ....

She says she has "finite power". Ask for precisely the largest number of days she can provide with her "finite power."

*any* FINITE number !

It is up to you to choose one in particular. And to succeed in describing which one.

Recall that the set of all finite things (or numbers) is infinite.

This method is similar to the robber's response when the victim asks him "how much money do you want?": "All the money in your pocket."

Method 2) Use the concept of "limits" Ask for as many days it would take to obtain a sum of 2 as terms in the series 1+1/2 + 1/4 + 1/8 + 1/16..... If the fairies knows any math she may argue that the series never reaches 2.

And she is right!

On the other hand I may argue that "in the limit" it does reach 2.

Yes but to reach that limit you need an infinity of additions. The serie is convergent, and you can go as close as you want to 2 in finite steps, but 2 itself requires an infinity of steps, and the fairy asks you to specify a precise number, actually the biggest you can specify precisely (through some algorithm, program, description) using a reasonable amount of paper. The better is to describe a growing function applied to some number. Although it looks a little bit ridiculous, the child solution: "9 + 9" contains the basic good idea: applying a growing function you know (or can program), like "+" on a big number that you know, like 9. Of course "9 * 9" is better, and "9^9" is still better, ... (?) ....

Method 3) Come up with a unprovably non-halting problem:

Again, you are anticipating on the next sort of fairy I will present later. The current fairy is somehow constructivist, and ask you to specify a number as big as you can describe, but it must be a precisely well defined number.

For example ask for as many days as required digits in PI to prove that PI has a single repetition of a form such that digits 1 to n match digits n+1 to 2n. For example 2^0.5 = 1.4142135... has a single repetition (1 4 match 1 4) in which digits 1 to 2 match digits 3 to 4. Similarly 79^0.5=8.8881944 and 147^0.5= 12.12435565. Note that the repetition must include all numbers 1 to n from the beginning and match all number n+1 to 2n The problem with this approach is I don't know for sure if PI is repeatable or non-repeatable (according to above requirements.) I don't even know if this problem is unprovable. All I know is that the probability for any irrational to have a single repeat is about 0.1111. For PI the probability is much lower since I already know PI to a large number of digits and as far as I can see it does not repeat. However, with this approach I could be taking chances.

Indeed.

Diagonalization clearly allows you to specify a number outside any given set of number, but I have not been able to weave it into this argument.

I will say more in my reply to Hal Finney who gives a good start.

Bruno

http://iridia.ulb.ac.be/~marchal/