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/
X-Google-Language: ENGLISH,ASCII
Received: by 10.54.63.19 with SMTP id l19mr144706wra;
Sat, 20 May 2006 05:14:18 -0700 (PDT)
Return-Path: <marchal.domain.name.hidden>
Received: from dorado.vub.ac.be (dorado.vub.ac.be [134.184.129.10])
by mx.googlegroups.com with ESMTP id v11si357425cwb.2006.05.20.05.14.16;
Sat, 20 May 2006 05:14:18 -0700 (PDT)
Received-SPF: neutral (googlegroups.com: 134.184.129.10 is neither permitted nor denied by best guess record for domain of marchal.domain.name.hidden)
Received: from mach.vub.ac.be (maxi.vub.ac.be [134.184.129.8])
by dorado.vub.ac.be (Postfix) with ESMTP id 50A481B0
for <everything-list.domain.name.hidden>; Sat, 20 May 2006 14:14:16 +0200 (CEST)
Received: by mach.vub.ac.be (Postfix, from userid 21099)
id 388478D12; Sat, 20 May 2006 14:14:16 +0200 (CEST)
Received: from [164.15.10.83] (post.ulb.ac.be [164.15.10.83])
by mach.vub.ac.be (Postfix) with ESMTP id 2E5838D0C
for <everything-list.domain.name.hidden>; Sat, 20 May 2006 14:14:15 +0200 (CEST)
Mime-Version: 1.0
Content-Type: multipart/alternative; boundary="Apple-Mail-82-168838863"
In-Reply-To: <446E3CB5.1070906.domain.name.hidden>
References: <14762723.1143066850497.JavaMail.root.domain.name.hidden> <200603241938.14450.quentin.anciaux.domain.name.hidden.be> <1143229104.805923.181410.domain.name.hidden.googlegroups.com> <200603242045.08484.quentin.anciaux.domain.name.hidden.be> <1143229759.310865.304480.domain.name.hidden.googlegroups.com> <44245849.3060503.domain.name.hidden.fr> <442485EE.6010907.domain.name.hidden.net> <44f38451d0bd50dafb206875eb78cd17.domain.name.hidden.ac.be> <446E3CB5.1070906.domain.name.hidden.net>
Message-Id: <0294de8517ff43d87c13519904c003a3.domain.name.hidden>
From: Bruno Marchal <marchal.domain.name.hidden>
Subject: Re: Smullyan Shmullyan, give me a real example
Date: Sat, 20 May 2006 14:14:06 +0200
To: everything-list.domain.name.hidden
X-Mailer: Apple Mail (2.623)
X-Spam-Checker-Version: maxi.ulb.ac.be SA 2.63 (2004-01-11)
X-Spam-Status: No, hits=0.0, level=
--Apple-Mail-82-168838863
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Le 19-mai-06, =E0 23:46, George Levy a =E9crit :
> 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=20
> incremented by 1 so this finite number could not be the largest. The=20
> trick is not to name a particular number but to specify a method to=20
> reach the unreachable.
Well, if *you* try to give the biggest natural number, *you* will never=20
stop, and you will not succeed in specifying a large number, and the=20
fairy will not make your wish coming true, and you will gain nothing.=20
It would be absurd not saying 10^100 under the pretext that you would=20
have prefer to live "(10^100)+1" years.
By trying to reach the unreachable, well, you are anticipating another=20
fairy which I will present to you once you will be able to diagonalize=20
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=20
=2E...
> She says she has "finite power". Ask for precisely the largest number=20
> 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=20
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=20
> 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=20
> take to obtain a sum of 2 as terms in the series 1+1/2 + 1/4 + 1/8 +=20
> 1/16..... If the fairies knows any math she may argue that the series=20
> 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=20
serie is convergent, and you can go as close as you want to 2 in finite=20
steps, but 2 itself requires an infinity of steps, and the fairy asks=20
you to specify a precise number, actually the biggest you can specify=20
precisely (through some algorithm, program, description) using a=20
reasonable amount of paper. The better is to describe a growing=20
function applied to some number. Although it looks a little bit=20
ridiculous, the child solution: "9 + 9" contains the basic good idea:=20
applying a growing function you know (or can program), like "+" on a=20
big number that you know, like 9. Of course "9 * 9" is better, and=20
"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=20
later. The current fairy is somehow constructivist, and ask you to=20
specify a number as big as you can describe, but it must be a precisely=20
well defined number.
> For example ask for as many days as required digits in PI to prove=20
> that PI has a single repetition of a form such that digits 1 to n=20
> match digits=A0 n+1 to 2n. For example 2^0.5 =3D 1.4142135... has a=A0=20
> single repetition (1 4 match 1 4) in which digits 1 to 2 match digits=20
> 3 to 4. Similarly=A0 79^0.5=3D8.8881944 and 147^0.5=3D 12.12435565. Note=
=20
> that the repetition must include all numbers 1 to n from the beginning=20
> and match all number n+1 to 2n The problem with this approach is I=20
> don't know for sure if PI is repeatable or non-repeatable (according=20
> to above requirements.)=A0 I don't even know if this problem is=20
> unprovable. All I know is that the probability for any irrational to=20
> have a single repeat is about 0.1111. For PI the probability is much=20
> lower since I already know PI to a large number of digits and as far=20
> as I can see it does not repeat. However, with this approach I could=20
> be taking chances.
Indeed.
>
> Diagonalization clearly allows you to specify a number outside any=20
> given set of number, but I have not been able to weave it into this=20
> argument.
I will say more in my reply to Hal Finney who gives a good start.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
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=
ooglegroups.com
For more options, visit this group at
http://groups.google.com/group/everyt=
hing-list
-~----------~----~----~----~------~----~------~--~---
--Apple-Mail-82-168838863
Content-Type: text/enriched; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Le 19-mai-06, =E0 23:46, George Levy a =E9crit :
<excerpt> Bruno Marchal wrote:
<excerpt><fixed>Now I think I should train you with diagonalization. I
give you an=20
exercise: write a program which, if executed, will stop on the biggest=20
possible natural number. Fairy tale version: you meet a fairy who=20
propose you a wish. You ask to be immortal but the fairy replies that=20
she has only finite power. So she can make you living as long as you=20
wish, but she asks precisely how long. It is up too you to describe=20
precisely how long you want to live by writing a program naming that=20
big (but finite) number. You have a limited amount of paper to write=20
your answer, but the fairy is kind enough to give you a little more if=20
you ask.
You can ask the question to very little children. The cutest answer I=20
got was "7 + 7 + 7 + 7 + 7" (by a six year old). Why seven? It was the=20
age of his elder brother!
Hint: try to generate an infinite set S of more and more growing and=20
(computable) functions, and then try to diagonalize it. S can be=20
{addition, multiplication, exponentiation, .... (?)....}. More hints=20
and answers later. I let you think a little bit before. (Alas it looks=20
I will be more busy in may than I thought because my (math) students=20
want supplementary lessons this year ...).
</fixed>
</excerpt>
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.
</excerpt>
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 ...
<excerpt>
Method 1) Use the fairy power against her.=20
</excerpt>
I see you like to live dangerously. Or to die dangerously should I say
=2E...
<excerpt>She says she has "finite power". Ask for precisely the
largest number of days she can provide with her "finite power."=20
</excerpt>
*any* FINITE number !=20
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.
<excerpt>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.=20
</excerpt>
And she is right!
<excerpt>On the other hand I may argue that "in the limit" it does
reach 2.
</excerpt>
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 "+"=20
on a big number that you know, like 9. Of course "9 * 9" is better,
and "9^9" is still better, ... (?) ....
<excerpt>
Method 3) Come up with a unprovably non-halting problem:=20
</excerpt>
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.
<excerpt>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=A0 n+1 to 2n. For example 2^0.5 =3D 1.4142135... has a=A0
single repetition (1 4 match 1 4) in which digits 1 to 2 match digits
3 to 4. Similarly=A0 79^0.5=3D8.8881944 and 147^0.5=3D 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.)=A0 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.
</excerpt>
Indeed.
<excerpt>
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.=20
</excerpt>
I will say more in my reply to Hal Finney who gives a good start.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
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=
ooglegroups.com
For more options, visit this group at
http://groups.google.com/group/everyt=
hing-list
-~----------~----~----~----~------~----~------~--~---
--Apple-Mail-82-168838863--
Received on Sat May 20 2006 - 08:15:23 PDT