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.

Method 1) Use the fairy power against her. She says she has "finite power". Ask for precisely the largest number of days she can provide with her "finite power." 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. On the other hand I may argue that "in the limit" it does reach 2.

Method 3) Come up with a unprovably non-halting problem: 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.

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.

George

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to