Comments on Problème de l'arrêt de problème de Post

Ruxor (2012-12-26T14:22:34Z)

@teky: Je pense qu'il y a là une certaine confusion.

Il y a d'abord une notion de « calculabilité au sens de Church-Turing » : cette notion admet plusieurs définitions, dont certaines peuvent, effectivement, évoquer la notion de temps. Mais il n'y a pas fondamentalement de temps dans la notion, pas plus qu'il n'y a de temps dans la notion de graphe connexe (qu'on pourrait définir comme un graphe où on peut aller de tout sommet à tout sommet en temps fini en parcourant les arêtes) ; et de fait, si on définit la calculabilité de Church-Turing au moyen du λ-calcul, il n'y a pas vraiment de temps qui apparaisse, juste une possibilité de réécriture. La notion de temps est, en revanche, utile pour l'intuition et pour justifier philosophiquement que la calculabilité de Church-Turing coïncide bien avec une notion effective de calculabilité (par exemple les calculs qu'on peut mener avec les lois de la physique dans notre monde — dans ce cas, bien formulée, la thèse de Church-Turing peut devenir un théorème).

Ensuite, il y a l'argument diagonal utilisé par Turing. Celui-ci dépend de fort peu de choses, et absolument pas, en aucune manière, d'une notion de temps. Il dit simplement que si on a une notion de calculabilité (que ce soit celle de Church-Turing ou une autre) qui permet d'énumérer effectivement les fonctions calculables de manière à avoir une fonction universelle, et qui permet certaines manipulations basiques évidentes, alors forcément la question de savoir si la m-ième fonction calculable est bien définie sur la n-ième entrée (ce qui dans le cadre de la calculabilité de Church-Turing se dit : « la m-ième machine de Turing s'arrête sur l'entrée n », mais ce n'est qu'un cas particulier) n'est elle-même pas calculable dans le même sens. C'est un argument complètement général.

Bref, Turing ne dit pas qu'il est impossible par aucun moyen de savoir si un programme va s'arrêter ou non, il dit qu'il est impossible de le faire de façon systématique dans le cadre de la même notion de calculabilité.

Donc si on veut « imaginer un processus physique qui étudie au niveau hardawre le fonctionnement du programme et dire à coup sur s'il va s'arrêter ou non », la conclusion de l'argument est que ce processus physique ne peut pas lui-même s'implémenter comme un programme. Or si c'est le cas, c'est que la notion de calculabilité qu'on a choisie n'est pas la bonne, il faut une notion de programme plus général qui puisse inclure le processus physique en question, et on retombe alors sur la même limitation.

teky (2012-12-26T13:42:27Z)

Il y a une chose qui me dérange toujours dans ce qu'on a appelé le problème de l'arrêt. C'est le temps. Tous les théorèmes et résultats mathématiques connus sont atemporels. La communication entre axiomes est instantanée (si cette phrase a un sens. Par contre l'indécidabilité à la Godel ne souffre ce handicap. Je crois que le mauvais grain a été introduit par la notion de calculabilité et machine de Turing. Je ne comprend pas pourquoi les mathématiciens ont accepté à introduire cette notion de temps fini alors que le temps est étranger aux mathématiques en général. Pour décider de l'arrêt ou non d'un programme je peux très bien imaginer un processus physique qui étudie au niveau hardawre le fonctionnement du programme et dire à coup sur s'il va s'arrêter ou non. Qu'en pensez vous.

ooten (2012-12-10T16:57:58Z)

@Ruxor : Oui effectivement, on a un exemple de cet algorithme. Q+ = 0,1,f(2),…,f(n) avec n aussi grand qu'il faut et f(k)=((k-1),k),((k-2),k),…,(1,k),(k,(k-1)),(k,(k-2)),…,(k,1) où (x,y) désigne le numérateur et le desnominateur d'un nombre rationnel.

Ruxor (2012-12-07T00:04:23Z)

@ooten: Effectivement, quand on énumère les rationnels on perd leur ordre naturel, mais ça n'a pas d'importance parce qu'on veut juste savoir s'il existe un n-uplet de rationnels vérifiant telle ou telle équation polynomiale, donc la seule chose qui importe est d'avoir un procédé algorithmique qui les énumère (pour les tester) et qui est sûr d'énumérer n'importe quel rationnel fixé à l'avance. Il n'y a pas de difficulté particulière à ce niveau-là.

justt (2012-12-06T23:09:47Z)

Je n'ai rien d'intéressant à dire, mais je voulais vous remercier pour vos billets particulièrement intéressants.

ooten (2012-12-06T23:05:47Z)

Aaaaah, encore de la très, très bonne vulgarisation !!! Parcontre je ne vois pas très bien pourquoi la résolubilité des équations polynomiales sur les rationnels devrait être dans le pire des cas semi-décidable et pas complètement indécidable. En effet existe-t-il un algorithme, au sens de Turing et manipulant seulement des entiers (ou alors des décimaux mais alors ce ne sont que des approximations des rationnels), permettant d'énumérer systématiquement et de façon ordonnée (pour justement être systématiquement énumérés et ne pas en louper) l'ensemble des n-uplets rationnels ? Je ne le crois pas car, malgré que l'ensemble des rationnels soit dénombrable, il me semble que la démonstration de cette dénombrabilité passe par une représentation dans le plan des couples (x,y) d'entiers représentants les numérateurs et les desnominateurs des nombres rationnels qui fait qu'on en perdrait son ordre total relativement à ses indices.
En outre il y a un truc qui me bouleverse c'est qu'il existe des énoncés dans le langage de l'arithmétique formelle du premier ordre indémontrables (et donc indécidables), j'en avais jamais eu conscience avant que tu me l'eus dit en réponse dans un précédent post. J'aimerais bien en connaître les ressorts et voir la gueule de ces propositions. Et il n'est pas évident aussi de comprendre pourquoi ces énoncés sont complètement indécidables.

DM (2012-12-05T20:37:15Z)

Pour ta discussion en note sur les énoncés de l'arithmétique, peut-être devrais-tu discuter du lien avec la hiérarchie arithmétique.

Ruxor (2012-12-05T18:42:24Z)

@Fab: Je pense qu'il vaut mieux que j'écrive une nouvelle entrée pour répondre à cette question et clarifier les confusions sous-jacentes. À suivre, donc.

Fab (2012-12-05T18:15:53Z)

Oui, d'accord, merci !
J'avoue que ces histoires de « propositions vraies non démontrables » me posent problème. Une proposition indécidable dans un système donné, je le le conçois plutôt bien, mais du vrai non démontrable (je sais que tu as déjà beaucoup écrit sur ce sujet) ??
Prenons par exemple un énoncé mathématique quelconque P et la théorie ZFC. Parmi les énoncés suivants, lesquels ont un sens ET sont parfaitement précis (ne supportent aucune ambiguïté dans leur interprétation) ?
a) P est vrai.
b) P est vrai dans ZFC.
c) P est vrai dans ZFC et on ne peut pas le montrer dans ZFC.
d) P est indécidable dans ZFC.
Si c) et d) ont un sens, sont-il incompatibles ?
Et selon que l'on suppose ZFC consistante ou pas, y a-t-il des cas de figure qui ne se posent pas ? etc.
(bon, okay on s'éloigne du sujet, désolé)

Ruxor (2012-12-04T17:11:29Z)

@Fab: En fait, je n'aurais sans doute pas dû parler de la hiérarchie hyperarithmétique pour parler des fonctions primitives récursives, parce que c'est un sujet assez différent, j'essayais de dresser un parallèle entre l'itération transfinie du saut de Turing (donc la hiérarchie hyperarithmétique, voire constructible) et l'itération transfinie du saut de Kleene (la hiérarchie de Grzegorczyk), mais j'ai peut-être plus embrouillé qu'autre chose.

Sur la différence entre démontrabilité et vérité, je viens d'ajouter une note (#2b).

Fab (2012-12-04T11:57:43Z)

Très joli post ! (oui, pas pu m'empêcher) Et bel effort de pédagogie !
… et que j'ai lu beaucoup plus facilement que le précédent(fonctions primitives récursives), mais qui du coup me donne envie de m'y replonger. Probablement, la hiérarchie hyperarithmétique (entre autres) nécessite un plus haut degré d'abstraction.
Et au passage, la technique de la blessure finie m'intéresse beaucoup (j'ai été très sage cette année. Si si).
Mais tout de même, dire que trouver un exemple naturel de problème intermédiaire serait « beaucoup plus impressionnant qu'une preuve de l'hypothèse de Riemann » me paraît très fort ! L'hypothèse de Riemann quand même (et tout ce qu'elle suscite de mystère, de quasi-ésotérisme, chez les mathématiciens parfois eux-mêmes…)

Sinon, naïvement, je croyais que les équations polynomiales sur les rationnels et les équations diophantiennes c'était la même chose (dans le sens que l'une des premières pût se réduire à une seconde…).
D'autre part je n'arrive pas vraiment à saisir ce qu'est le « problème de la vérité arithmétique » que je confondais moi-même avec la « théorémitude » de l'arithmétique de Peano (de toute évidence totalement différents puisque le second que je crois comprendre, seulement, est semi-décidable).