Hydre de Kirby
J'ai regardé récemment une vidéo sur l'hydre de Kirby. Je ne sais pas trop quoi penser de la conclusion : s'applique-t-elle au monde réel (à supposer qu'on vive indéfiniment) ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il n'y a rien de bien mystérieux là-dessous. Ce qui est regrettable c'est que le type passe 3 plombes à t'expliquer ce qu'est un ordinal, et sur la fin, là où ça devient plus difficile à suivre, il accélère comme un malade.
Tape "suites de Goodstein" dans google, c'est un problème très similaire peut-être plus facile à appréhender.
Quant aux applications au monde réel elles me paraissent utopiques : si Hercule donne un coup par seconde, le temps qu'il va mettre à flinguer son hydre est immensément plus grand que l'espérance de vie de la Terre...
Moi je dirais : oui la solution est viable dans la "vraie vie" de la Terre éternelle.
La raison pour laquelle certains énoncés arithmétiques, tel que "l'hydre sera vaincu peu importe la stratégie d'Hercule" (enfin, une traduction de cette phrase en langage arithmétique), sont indécidables, c'est que les axiomes de l'arithmétique de Peano n'excluent pas l'existence d'entiers chelous supérieurs à tous les entiers intuitifs (ceux qu'on utilise pour compter : 0, 1, 2, 3, etc.). Le vrai terme est "entiers non standard". Il existe des structures $(\Bbb N',0,1,+,\times)$ qui satisfont les axiomes de Peano, et qui contiennent donc tous les entiers intuitifs (0, 1, 1+1=2, 2+1=3, etc. donc $\Bbb N\subset \Bbb N'$), mais qui contiennent aussi des $n'\in\Bbb N'$ tels que $\forall n\in\Bbb N, n'>n$. Donc certains énoncés peuvent être vrais pour $\Bbb N$ mais pas pour tous les $\Bbb N'$, et donc non démontrable dans la théorie de Peano. C'est le cas de "l'hydre sera vaincu peu importe la stratégie d'Hercule". C'est un peu une bizarrerie de la logique à première vue.
Mais l'hydre de la "vraie vie", lui, possède un nombre de têtes qui est un entier standard. Donc ce qui compte pour savoir si "l'hydre sera vaincu peu importe la stratégie d'Hercule" est vérifié dans la réalité, c'est que cet énoncé soit vrai pour $\Bbb N$ l'ensemble des entiers intuitifs. Et c'est le cas.
Je vois bien que ma question paraît naïve aux yeux de certains compte tenu des réponses que j'ai reçues, mais je suis vraiment gêné. D'un côté, je me dis "on s'en fiche", c'est comme quand on passe par les nombres complexes pour résoudre un problème sur les nombres réels ; d'un autre côté, je me dis qu'il y a quelque chose de plus profond... et à vrai dire, je suis vraiment gêné par ce nombre $\omega$.
Attention, il ne faut pas confondre ordinaux infinis et entiers non standards. S'il existe des entiers non standard ils vont indexer des chambres qui sont situées tout à droite du RDC de l'hôtel (bonjour la dame qui fait le ménage !), mais tu vois bien qu'ils sont tous $< \omega$
@rebellin : je t'explique pourquoi on ne peut pas énoncer le problème de l'hydre dans Peano : il suffit de reprendre les explications de Calli. Si tu voulais l'écrire il faudrait que tu dises : "je suppose que l'hydre a un nombre standard de têtes". Et ça tu ne peux pas, car un modèle non standard ne sait pas qu'il est non standard. En particulier il est incapable de différencier ses éléments standards des autres. C'est un peu la chaîne de Darwin, qui part d'un singe pour arriver à un homme. Pourtant, le fils d'un singe est toujours un singe, et le père d'un homme est toujours un homme.
Par contre, le truc des suites de Goodstein peut s'écrire dans Peano. Mais ce qui est marrant c'est que l'énoncé (dans Peano) est plus difficile et plus long à écrire que la démonstration (dans ZFC).
- une formule $P(h)$ qui dit si un entier $h$ code une hydre
- une formule $Q(n)$ qui dit si un entier $n$ est une listes d'hydres (elle utilise la formule $P$)
- une fonction $\ell(n)$ qui donne la longueur de la liste $n$
- une fonction $f(n,i)$ qui a un $n$ codant une liste d'hydres associe la $i$-ième hydre
- une relation $S(h_1,h_2)$ qui dit si l'hydre $h_2$ est obtenu à partir de l'hydre $h_1$ auquel on a coupé une tête (et d'autres têtes ont éventuellement repoussé)
- finalement l'énoncé $$\forall n, \,Q(n) \Rightarrow ([\forall i,\, i<\ell(n) \Rightarrow S(f(n,i),f(n,i+1))] \wedge f(n,\ell(n)) = \text{l'hydre sans tête}).$$
Dans un modèle non standard de Peano, on risque d'avoir des entiers non standard codant des hydres d'après la formule $P$, mais ce ne seront pas de vraies hydres. Donc on ne peut pas trouver de formule $R(h)$ qui dit si $h$ est un entier standard qui code une hydre, mais je pense qu'on peut écrire une formule $P$ telle que tout entier standard $h$ vérifie "$P(h) \Rightarrow h$ code une hydre". C'est suffisant pour formaliser le problème de manière satisfaisante.Bon, bien sûr, on peut "taffer" pour approcher ça artificellement dans Peano, mais didactiquement, c'est désastreux puisqu'il est prouvé que seule l'alternance de quantificateurs est ce qui fait monter les marches de la complexité en maths.