Comments on Qui peut dire le nombre le plus grand ?

ooten (2017-09-20T12:31:15Z)

@Ruxor : oui effectivement d'autant que la thèse de Church ou Church-Turing n'établit pas d'équivalence entre ZF(C), PA ou autres systèmes axiomatiques sur les ensembles et la machine de Turing contrairement à ce que je laissais supposer. Ces systèmes formels et la machine de Turing ne permettent simplement pas de définir et d'exprimer les mêmes grands entiers.

Ruxor (2017-09-20T09:25:12Z)

@ooten: Je ne trouve pas que ça ait de rapport avec la thèse de Church-Turing : c'est un avatar du théorème de Gödel, qui nous apprend qu'un système formel (ici ZFC) compatible en un certain sens avec l'arithmétique ne peut pas prouver certains énoncés arithmétiques pourtant vrais, notamment sa propre consistance, consistance qui se traduit précisément par le fait qu'un certain programme (celui qui énumère toutes les démonstrations à la recherche d'une contradiction) ne va jamais finir ; transformer ça en une affirmation sur le castor affairé est alors presque évident. Ça ne dit pas grand-chose ni sur ZFC ni sur la thèse de Church-Turing mais juste sur les limitations (inévitables) de la logique du premier ordre. Ou pour le dire encore différemment et de façon plus informelle : pour rester calculable, la logique du premier ordre doit forcément abandonner la prétention d'être capable de tout prévoir concernant les machines de Turing, puisque les machines de Turing ne peuvent pas tout prévoir concernant les machines de Turing.

ooten (2017-09-20T07:32:19Z)

Merci Jonas pour ce lien, j'en apprends plus sur le busy beaver qui est vraiment étonnant !!! Et notamment, je cite " To be clear, it was long understood that there’s some computer program that halts if and only if set theory is inconsistent—and therefore, that the axioms of set theory can determine at most k values of the Busy Beaver function, for some positive integer k ", C'est vraiment étonnant, non ? Pour moi ça remet en cause la thèse de Church-Turing qui c'est vrai, n'est pas d'un grand intérêt.

jonas (2017-09-15T12:14:29Z)

Scott Aaronson just published a new lecture on this one: <URL: https://www.scottaaronson.com/blog/?p=3445 > Big Numbers.

Ruxor (2016-10-26T13:11:15Z)

@jonas: Fixed. I also added the full title, so it can be found by Google in case the link breaks again in the future.

jonas (2016-10-26T10:05:00Z)

It seems your link to la thèse de Jan-Carl Stegert is broken.

Baptiste (2013-01-20T10:55:50Z)

Deux liens :
Un article de Scott Aaronson traduit en français : http://blog.smwhr.net/2007/09/30/la-course-aux-grands-nombres/
Un jeu semblable, limité à des programmes de 512 caractères en c : http://news.ycombinator.com/item?id=1539764

Ruxor (2013-01-19T18:23:09Z)

Rechercher des réels strictement positifs très petits revient exactement à rechercher des réels très grands (en passant à l'inverse), et comme on ne considère de toute façon que des ordres de grandeur cela revient encore à chercher des entiers très grands, ce dont je parle.

Wolff (2013-01-19T15:42:26Z)

Pas tout compris, donc excuse ma question, mais: recherche-t-on avec autant de fécondité le "plus petit réel strictement positif" et, le cas échéant, parvient-on aux mêmes raisonnements?

Laurent (2013-01-17T12:41:53Z)

"Chuck Norris a déjà compté jusque l'infini. Deux fois."

Nick (2013-01-17T11:32:32Z)

@Fred : 2↑63, c'est 9 223 372 036 854 775 808, c'est franchement pas énorme. C'est sensiblement moins que le nombre de cellules humaines sur Terre ou que le nombre d'octets que l'on peut stocker dans tous les disques durs de la planète, par exemple. 2↑63 m, c'est une distance qui a un sens physique. On est très très loin du nombre de Graham.

@Ruxor : la connaissance que tu sembles avoir accumulée sur les ordinaux me semble vraiment du même ordre que celle que doivent posséder les gens dont c'est le métier. Est-ce que c'est « juste » un truc qui te fascine ou est-ce que tu as des projets de recherche à ce sujet (« recherche » comme dans « publier des articles, » hein, il me paraît clair que tu fais *déjà* de la recherche sur ces objets si l'on définit « recherche » de manière un peu plus large — et plus noble).

Fred le marin (2013-01-17T03:36:36Z)

Bonjour,

2 puissance 63 est construit par :
- Je place un (1) grain de riz sur la première case (en bas à droite) d'un jeu d'échec - ou échiquier -.
- Je double le nombre de grains case suivante (vers la gauche, puis en remontant d'une ligne et en repartant de la droite).
- Ainsi de suite (je redouble les grains de la case précédente)…
- Je regarde le nombre de grains case finale.
Ce nombre peut être stocké (à une unité près) dans un "long" en JAVA.
La durée de ma vie (en secondes) tenant sur un UINT32 (en C), je ne vois pas pourquoi il faudrait se faire plus de noeuds au cerveau.
Laissons venir !
(P.S. les cases sont bien indexées de n = 0 à 63 : 2 puissance n grains sur la case n, - humour -)
Enfin, ce nombre m'apparaît déjà assez grand.


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: aa18f9


Recent comments