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.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Fri May 19 2006 - 18:05:59 PDT