Les ordinateurs peuvent-ils résoudre tous les problèmes ?

[yat]

Je crois (sans être suffisement renseigné pour en être sur) que c'est parce que dans la phrase suivante "une machine ne peut décider l'arrêt de n'importe quelle machine", tu oublies le "n'importe quelle". Autrement dit il serait possible de trouver une solution dans un cas donné, mais pas une solution à tous les cas de machine de Turing possibles.

Ben non, je ne l'oublie pas, ce "n'importe lequel" c'est bien ça le problème. Je sais bien que dans la réalité une machine de turing pourra prédire que certaines autres vont s'arréter ou boucler, et que c'est parce qu'il y a des cas qui resteront inaccessibles qu'on dit qu'une telle machine n'existe pas... et c'est bien ça que je n'arrive pas à comprendre. C'est bien la démo, telle qu'elle est donnée par spi100 ou sur wikipedia, ou sur à peu près tout ce que j'ai trouvé sur le net, qui me pose problème : D'une part il me semble qu'on peut faire exactement la même pour démontrer qu'une fonction retour() n'existe pas, alors que celle-ci existe bien. Du coup une des deux démos est juste, l'autre fausse. Et je n'arrive pas à comprendre ce qui est faux dans la mienne et juste dans la vraie.
D'autre part, il me parait très facile de décrire un algorithme permettant de déterminer sur un autre algorithme va se terminer ou partir en boucle, se basant sur le postulat qu'on ne manipule nécessairement qu'un nombre fini d'états. Je sais bien que ça ne correspond pas à l'énoncé parce qu'une machine de turing est sensée avoir un ruban extensible à l'infini. Je comprends bien aussi qu'il faudra toujours une machine beaucoup plus complexe que celle sur laquelle tourne l'algorithme à tester, ce qui fait que quel que soit la machine que l'on utilise pour tester, il existera une infinité d'algorithmes trop complexes et qui nécessiteront une machine plus complexe pour être testés. Mais la démo ne reflète absolument pas cet état de fait et, comme c'est une démo par l'absurde, se base sur une contradiction. C'est cette contradiction qui, pour moi, n'en est pas une.
-----

[spi100]

D'autre part, il me parait très facile de décrire un algorithme permettant de déterminer sur un autre algorithme va se terminer ou partir en boucle, se basant sur le postulat qu'on ne manipule nécessairement qu'un nombre fini d'états. Je sais bien que ça ne correspond pas à l'énoncé parce qu'une machine de turing est sensée avoir un ruban extensible à l'infini.

Ce n'est pas si facile, je reprend l'exemple de la wikipedia

function findTwinPrimeAbove(int N)
int p := N
loop
if p is prime and p + 2 is prime
return
else
p := p + 1

Savoir si ce programme s'arrête demande de savoir s'il existe un nombre premier tel que p et p + 2 soit premier. Or pour le moment personne ne sait s'il existe. Si le halting programme existait nous pourrions de façon automatique résoudre toutes les conjectures mathématiques sur les nombres entiers.

Je comprends bien aussi qu'il faudra toujours une machine beaucoup plus complexe que celle sur laquelle tourne l'algorithme à tester, ce qui fait que quel que soit la machine que l'on utilise pour tester, il existera une infinité d'algorithmes trop complexes et qui nécessiteront une machine plus complexe pour être testés. Mais la démo ne reflète absolument pas cet état de fait et, comme c'est une démo par l'absurde, se base sur une contradiction. C'est cette contradiction qui, pour moi, n'en est pas une.

Si par complexité tu entends la capacité à émuler,
cette démo permet justement d'affimer que les machines de turing ne sont pas suffisament complexes pour émuler une machine capable de décider de l'arrêt de n'importe quel programme. La complexité des machines de Turing butte sur une limite.

[yat]

Ce n'est pas si facile, je reprend l'exemple de la wikipedia (...) Savoir si ce programme s'arrête demande de savoir s'il existe un nombre premier tel que p et p + 2 soit premier. Or pour le moment personne ne sait s'il existe. Si le halting programme existait nous pourrions de façon automatique résoudre toutes les conjectures mathématiques sur les nombres entiers.

Oui, j'ai bien compris ou se situait la difficulté de cet exemple. Mais même là, si rien n'est infini, la valeur de p aura donc une valeur limite, et passé cette limite (si, bien entendu, on n'a pas trouvé de solution avant, ce qui résoud le problème) elle se retrouvera à zéro et recommencera sa boucle jusqu'à atteindre la valeur N. A ce moment là la machine est exactement dans le même état que lors de la première itération. On peut donc être sur qu'elle ne s'arrêtera jamais.

Si par complexité tu entends la capacité à émuler, cette démo permet justement d'affimer que les machines de turing ne sont pas suffisament complexes pour émuler une machine capable de décider de l'arrêt de n'importe quel programme. La complexité des machines de Turing butte sur une limite.

Je ne saurais pas vraiment définir la capacité à émuler... par complexité, j'entends surtout la mémoire disponible. En gros, une machine dont les rêgles comptent M états différents, un ruban de N cases pouvant contenir P symboles différents pourra se trouver dans M*P^N états différents au sens large, c'est à dire que si la machine se trouve dans un état dans lequel elle a déjà été auparavant, tout va se passer une deuxième fois de la même manière, avant d'atteindre une troisième fois cet état et boucler à l'infini. Du coup, la machine qui va la tester (et donc l'émuler, tu m'as bien démasqué sur ce coup là ) devra dans le pire des cas être capable de garder en mémoire ces M*P^N états différents, car potentiellement ils peuvent être tous parcourus avant que ca boucle. J'imagine que le nombre d'états, de cases de ruban ou de symboles possibles de cette machine-émulateur devront être beaucoup plus grands que M, P et N. C'était juste ça que j'entendais par "machine plus complexe". La démo ne fait absolument pas intervenir ces notions, et se contente d'aboutir sur une contradiction qui pour moi n'a rien à voir, et n'en est pas une. En effet, sans se soucier de la méthode d'implémentation, le simple fait qu'une fonction halt() nécessiterait (si elle existait) un paramètre m'empêche à aboutir à une contradiction.

[spi100]

Oui, j'ai bien compris ou se situait la difficulté de cet exemple. Mais même là, si rien n'est infini, la valeur de p aura donc une valeur limite, et passé cette limite (si, bien entendu, on n'a pas trouvé de solution avant, ce qui résoud le problème) elle se retrouvera à zéro et recommencera sa boucle jusqu'à atteindre la valeur N. A ce moment là la machine est exactement dans le même état que lors de la première itération. On peut donc être sur qu'elle ne s'arrêtera jamais.

Non, tu ne peux pas en être sur, car tu ne sais pas (comme tout le monde en ce moment ), s'il existe p et p + 2 premiers.

Je ne saurais pas vraiment définir la capacité à émuler...
par complexité, j'entends surtout la mémoire disponible.

La question de la mémoire ne se pose pas pour les machines de Turing car par définition, cette mémoire est infinie. Je pense que c'est pour ça que la démo ne fait pas apparaitre cette notion de mémoire.

[yat]

Non, tu ne peux pas en être sur, car tu ne sais pas (comme tout le monde en ce moment ), s'il existe p et p + 2 premiers.

Je crois que tu as mal lu ce que j'ai écrit . Relis une fois le passage que tu as cité

La question de la mémoire ne se pose pas pour les machines de Turing car par définition, cette mémoire est infinie. Je pense que c'est pour ça que la démo ne fait pas apparaitre cette notion de mémoire.

Oui, c'est bien ça qui me chagrine... pour moi l'obstacle principal est justement cette infinité. Elle est complêtement laissée de coté dans la démo, se basant sur une toute autre contradiction.

[spi100]

Je crois que tu as mal lu ce que j'ai écrit . Relis une fois le passage que tu as cité

Oui, tu as raison j'ai lu trop vite. Tu considères encore un ordinateur avec une mémoire limitée : une fois que la mémoire est saturée le programme recommence à 0. Mais à nouveau en supposant une taille limitée, tu sors du cadre des machines de Turing. Jiav a raison, la mémoire infinie est une hypothèse extrêmement importante.

[yat]

Tu considères encore un ordinateur avec une mémoire limitée : une fois que la mémoire est saturée le programme recommence à 0. Mais à nouveau en supposant une taille limitée, tu sors du cadre des machines de Turing. Jiav a raison, la mémoire infinie est une hypothèse extrêmement importante.

Oui, je suis tout à fait d'accord avec ça.
Mes propos doivent prêter à confusion, j'ai l'impression que tu ne vois pas bien ce qui me bloque :
-Il est bien clair pour moi que, dans le cadre de machines finies, pour toute machine halt() donnée, il existera une machine avec trop d'états différents pour être testée par halt().
-Je comprends bien aussi que dans le cadre de machines infinies, la méthode bourrin (qui consiste à noter tous les états de la machine testée en sachant que si elle ne s'arrète pas on passera nécessairement plusieurs fois dans le même état) ne peut plus s'appliquer. Mais il ne s'agit là que d'une implémentation que j'en propose dans un cadre fini. Le fait que cette méthode bien précise ne soit pas applicable pour une machine infinie ne prouve pas qu'il n'existe pas de méthode d'implémentation de la machine halt().
-Je conçois bien, intuitivement, que dans un cas comme dans l'autre, il semble difficile d'imaginer une machine qui soit capable de résoudre ce problème pour toute autre machine. Mais comme la réalité est parfois contre-intuitive, j'aimerais bien en comprendre la démonstration.

Le problème, c'est que pour moi (oui, je sais bien, je me trompe mais je ne vois pas où ) cette démonstration est fausse : ce qui aboutit à une contradiction, c'est l'absence d'un cas terminal dans une fonction récursive, et pas la nature de la fonction halt(). Du coup, avec l'exemple de la fonction retour(), je peux appliquer exactement le même raisonnement, et aboutir à la conclusion que retour() ne peut pas exister, ce qui est bien évidemment faux

[spi100]

Bon ok, il faut comprendre ce qui cloche dans ta démo.

[yat]

Bon ok, il faut comprendre ce qui cloche dans ta démo.

C'est à peu près ça. Plus précisément, trouver ce qui fait qu'en passant de la machine halt() à la fonction retour(), la démo devient fausse.
Je te remercie d'ores et déjà pour ta patience et ta bonne volonté
A ta place ça ferait longtemps que j'aurais laché l'affaire

[spi100]

Yat,

Je crois que j'ai compris ce qui cloche dans ton raisonement.

retour_faux(p)
{
if ( retour(p,p) == false )
return true
else
return false
}

retour_faux est représenté par une chaîne de caractères que l'on nomme s. Rien n'empêche d'appliquer retour_faux sur s.

en d'autre terme tu te retrouves avec le programme recursif suivant

bool retour_faux()
{
if ( retour_faux() == false )
return true
else
return false
}

En tant que développeur, je peux te guarantir que ton programme va partir dans une récursion infinie, en pratique tu exploseras la pile et le programme s'arrêtera. Dans la théorie des machines de Turing, ton programme ne s'arrêtera jamais car la pile est supposée infinie. Donc inutile d'attendre que retour_faux() te retourne une valeur, elle ne te retournera jamais rien. Donc tout raisonnement sur la valeur de retour_faux() ne vaut rien car cette valeur n'existe pas.

Ainsi la déduction suivante

si retour_faux(s) renvoie true alors retour(s) = true et retour_faux(s) renvoie false.
si retour_faux(s) renvoie false alors retour(s) = false et retour_faux(s) renvoie true.

ne peut pas se faire car elle s'appuie sur une quantité qui n'existe pas :la valeur de retour de retour_faux(s) .

[yat]

En tant que développeur, je peux te guarantir que ton programme va partir dans une récursion infinie, en pratique tu exploseras la pile et le programme s'arrêtera. Dans la théorie des machines de Turing, ton programme ne s'arrêtera jamais car la pile est supposée infinie. Donc inutile d'attendre que retour_faux() te retourne une valeur, elle ne te retournera jamais rien. Donc tout raisonnement sur la valeur de retour_faux() ne vaut rien car cette valeur n'existe pas.

Oui, c'est exactement ce que je dis : le problème vient d'un appel récursif sans cas terminal. Donc, en l'occurence, de la démonstration. Parce que dans les faits, la fonction retour() existe.

Alors je comprends très bien en quoi tu vois que le raisonnement ne marche pas. Le truc c'est que pour moi le raisonnement sur la fonction halt() est exactement le même.

Plus précisément, trouver ce qui fait qu'en passant de la machine halt() à la fonction retour(), la démo devient fausse.

[spi100]

Alors je comprends très bien en quoi tu vois que le raisonnement ne marche pas. Le truc c'est que pour moi le raisonnement sur la fonction halt() est exactement le même.

Oui, effectivement, mais c'est parce que la démo telle que je la présente est mal posée. Il vaut mieux partir de la démo originale avec la machine de Turing, c'est moins ambigue.
Dans cette démo, l'algorithme retour_faux() appliqué à lui-même ne peut pas marcher car il ne retourne pas de valeur. Par contre l'objection ne tient pas si on considère la fonction halt() plutot que retour() car si elle ne retourne rien, justement elle ne s'arrête pas.
La subtilité réside peut être dans le fait qu'un algo récursif sans condition d'arrêt, est aussi un programme qui ne s'arrêtera jamais.

[yat]

Oui, effectivement, mais c'est parce que la démo telle que je la présente est mal posée. Il vaut mieux partir de la démo originale avec la machine de Turing, c'est moins ambigue.

Mmmhhh... j'ai regardé attentivement la démo de wikipedia, la tienne m'a l'air de revenir au même... mais bon, là encore, doit y avoir un truc que je vois pas

Dans cette démo, l'algorithme retour_faux() appliqué à lui-même ne peut pas marcher car il ne retourne pas de valeur.

Oui, en effet ça part en couille, mais comme je le vois, c'est plutôt au niveau de l'appel qu'au niveau de la fonction en elle-même que le problème se pose. Pour appliquer la fonction à elle-même, sans autre précision, on est obligé de chainer une liste infinie d'arguments, puisque chaque argument contient la fonction et ses arguments. C'est dans l'idée en elle-même que je trouve que ça cloche...

Par contre l'objection ne tient pas si on considère la fonction halt() plutot que retour() car si elle ne retourne rien, justement elle ne s'arrête pas. La subtilité réside peut être dans le fait qu'un algo récursif sans condition d'arrêt, est aussi un programme qui ne s'arrêtera jamais.

Ouais, à ce niveau là c'est vrai que c'est pas exactement la même chose, mais c'est plutôt une pirouette. En fait, si on ne se place pas d'un point de vue de développeur, le comportement de la fonction boucle boucle_si_halt() sur elle-même, c'est la limite d'une suite booléenne... 0=" la fonction s'arrète", 1="la fonction part en boucle", et Un+1=1-(Un)... Ce que la démo dit, c'est que cette suite n'a pas de limite, pourtant la rêgle qui passe de Un à Un+1 est bien définie.

[spi100]

Bon voici 3 autres preuves proposées par G. Chaitin

http://www.cs.auckland.ac.nz/CDMTCS/...n/georgia.html

Here come three proofs that the halting problem is unsolvable. One proof considers that function F(N) defined to be either one more than the value of the Nth computable function applied to the natural number N, or zero if this value is undefined because the Nth computer program does not halt on input N. F cannot be a computable function, for if program N calculated it, then one would have F(N) = F(N)+1, which is impossible. But the only way that F can fail to be computable is because one cannot decide if the Nth program ever halts when given input N.

The proof I have just given is of course a variant of the diagonal method which Georg Cantor used to show that the real numbers are more numerous than the natural numbers (Courant and Robbins, 1941). Something much closer to Cantor's original technique can also be used to prove Turing's theorem. The argument runs along the lines of Bertrand Russell's paradox (Russell, 1967) of the set of all things that are not members of themselves. Consider programs for enumerating sets of natural numbers, and number these computer programs. Define a set of natural numbers consisting of the numbers of all programs which do not include their own number in their output set. This set of natural numbers cannot be recursively enumerable, for if it were listed by computer program N, one arrives at Russell's paradox of the barber in a small town who shaves all those and only those who do not shave themselves, and can neither shave himself nor avoid doing so. But the only way that this set can fail to be recursively enumerable is if it is impossible to decide whether or not a program ever outputs a specific natural number, and this is a variant of the halting problem.

For yet another proof of the unsolvability of the halting problem, consider programs which take no input and which either produce a single natural number as output or loop forever without ever producing an output. Think of these programs as being written in binary notation, instead of as natural numbers as before. I now define a so-called Busy Beaver function: BB of N is the largest natural number output by any program less than N bits in size. The original Busy Beaver function measured program size in terms of the number of states in a Turing machine instead of using the more correct information-theoretic measure, bits. It is easy to see that BB of N grows more quickly than any computable function, and is therefore not computable, which as before implies that the halting problem is unsolvable.

[yat]

Bon voici 3 autres preuves proposées par G. Chaitin

http://www.cs.auckland.ac.nz/CDMTCS/...n/georgia.html

Merci de te coltiner les recherches à ma place

Avec la troisième démo, j'ai enfin quelque chose que je comprends ! Et c'est un peu une vraie démonstration de l'intuition que j'avais au début. On reste là sur quelque chose de fortement lié au caractère infini du truc, et surtout au fait que quel que soit la machine A que l'on imagine pour déterminer le résultat d'une autre machine, il existera toujours forcément une machine B non calculable par A, parce qu'elle est plus complexe, ou un truc dans le genre ('fin j'me comprends ).

Pour la première, par contre, ça me fait le même effet qu'avec la démo basée sur le boucle_si_halt. Le problème est toujours qu'appliquer la fonction sur le nombre N (qui définit l'algorithme) n'a pas de sens, puisque l'algorithme N a besoin d'un paramètre pour fonctionner... : C'est le "function F(N) defined to be either one more than the value of the Nth computable function applied to the natural number N" qui pour moi n'a pas de sens...

Bon, je te remercie pour ta persévérance, maintenant que j'ai une démo que je comprends, je pense que ça ne sert plus à grand chose de se prendre la tête sur celle que je capte pas

[spi100]

Merci de te coltiner les recherches à ma place

De rien, ce sont des choses que j'avais déjà lues ( mais pas forcemment comprises ). Comme c'est dans un article sur le théorème de Goedel, ce n'est pas evident à trouver avec un moteur de recherche.

[invited494020f]

Bonjour, Dans le temps je travaillais sur les spleen-functions, qui servent à calculer les points d'une latte souple hypothétique passant par certains points imposés (construction navale).
Ces points sont calculés par itération, car la fonction f(y) est intimement mêlée dans la fonction: y=f(x, f(y)) et est donc difficile à calculer de façon analytique. On procède donc par suppositions d'"y" et on fait converger la fonction en faisant diminuer, par extrapolation, l'écart entre l'"y" supposé et obtenu. Le nombre des boucles est limitée par la précision sur "y" exigée. Il arrive que, dans des cas un peu extrêmes, le nombre d'itérations dépasse le raisonnable. Pour cette raison on fixe un nombre limite de boucles, 0 au départ et incrémenté à chaque boucle et qui, sa limite atteinte, fait sortir de la boucle et affiche un message d'erreur. C'est nécessaire, car des boucles infinis ont été constatées dans des cas où la latte "cassait", autrement dit la fonction était discontinue, ou bien "y" devenait trop grand ou trop petit pour la capacité numérique de la machine. C'est une précaution à prendre.
Je pense que c'est une illustration pratique de l'affirmation que les machines ne peuvent pas tout calculer.

[invite6c250b59]

Dans le temps je travaillais sur les spleen-functions,

Est-ce que ça a un rapport avec les spline function?

[invited494020f]

Est-ce que ça a un rapport avec les spline function?

C'en est, mais j'en ai vu des orthographes très variées et j'ai adopté celle-ci, car elle m'ennuyait beaucoup!

[inviteb7bc207b]

Le problème de la machine de Turing est un problème théorique. Dans la pratique je ne connais aucun programme qui soit embêté par cette limitation

C'est comme si on arrêtait de faire les math parce que selon Gödel il existe des propositions indémontrables!

[invite6c250b59]

Dans la pratique je ne connais aucun programme qui soit embêté par cette limitation

Ah bah si quand même: les programmateurs aimeraient certainement avoir un débuggeur qui leur indique si leur programme est parti en vrille ad vitam aeternam ou bien s'il va finir par pondre quelquechose dans un délai raisonable. Ce serait possible si le problème de l'arrêt était résolvable.

[inviteb7bc207b]

Oulà Jiav!

Dans la pratique l'arrêt d'un programme en vrai n'a rien, mais rien à voir avec le problème de la machine de Turing.

Un débugger n'est pas un programme qui prévoit l'arrêt d'un autre... (il fallait le rappeller).

[invite6c250b59]

Oulà Jiav!

Oulala!

Dans la pratique l'arrêt d'un programme en vrai n'a rien, mais rien à voir avec le problème de la machine de Turing.

Certes, mais l'impossibilité de savoir si le programme arrête ou non a certainement à voir avec le halting problem. Of course!

Un débugger n'est pas un programme qui prévoit l'arrêt d'un autre... (il fallait le rappeller).

Bien sur... puisque c'est impossible.

Mais si c'était possible, alors les débuggeurs pourraient se baser là-dessus: je prends un programme à débugger, puis j'en fait n versions avec chacune un mini programme qui compte le temps que ça prend, et renvoi une valeur si et seulement si le temps est en-dessous d'une valeur déterminée (chaque version ayant une valeur différente), sinon le mini-programme compte les nombres premiers jusqu'au dernier Ensuite je teste si chacune de ses versions s'arrête ou non, ce qui me permet de savoir en combien de temps le programme arrête.

Ça te serait pas utile comme fonction dans un débuggeur? Bien sur un débuggeur "traditionnel" fait d'autres choses, mais je suis assez persuadé que si le problème de l'arrêt était résolvable, alors la façon même de programmer serait complètement différente. En d'autres termes, ce que tu dis n'est vrai que dans un monde où toute la programmation est justement faite en fonction de cette contrainte: tu ne la vois plus parce qu'elle est trop fondamentale.

[inviteb7bc207b]

A ton avis Jiav, le théorème de Gödel a-t-il un impact sur les mathématiques ? Fait-on des math différemment ? NON !

Pour l'informatique c'est la même chose.

La plupart des conditions d'arrêt sont triviaux. Certes on peut faire des erreurs qui fait qu'une boucle part en "sucette" mais ça reste trivial.

[spi100]

A ton avis Jiav, le théorème de Gödel a-t-il un impact sur les mathématiques ? Fait-on des math différemment ? NON !

Pour l'informatique c'est la même chose.

La plupart des conditions d'arrêt sont triviaux. Certes on peut faire des erreurs qui fait qu'une boucle part en "sucette" mais ça reste trivial.

Oui effectivement, ça ne change rien à l'informatique, mais là il s'agit d'une discution de physique.
Dans une discussion du type "le réel est il calculable?", je trouve parfaitement normal de discuter des limites de la calculabilité.

[invite6c250b59]

A ton avis Jiav, le théorème de Gödel a-t-il un impact sur les mathématiques ?

Oui

Fait-on des math différemment ?

Oui.

Pour l'informatique c'est la même chose.

Oui.

La plupart des conditions d'arrêt sont triviaux.

Non.

Certes on peut faire des erreurs qui fait qu'une boucle part en "sucette" mais ça reste trivial.

Disons que tu ne vois que celles qui sont triviales.

[inviteb7bc207b]

J'aimerais bien avoir plus de précisions sur les deux premières réponses.

[spi100]

La plupart des conditions d'arrêt sont triviaux. Certes on peut faire des erreurs qui fait qu'une boucle part en "sucette" mais ça reste trivial.

Ce n'est pas forcemment un problème trivial.
Si un programme H décidant de l'arrêt de n'importe quel programme P existait, je pourrais résoudre n'importe quelle question d'arithmétique.

Imaginons une proposition du type
"Il existe i tel que f(i)=0"

Cette proposition peut être quelque chose du genre
"il existe i > 1 tel que i et i +2 sont premiers", où n'importe quelle autre conjecture arithmétique encore non résolue à ce jour.

Si j'ecris un programme de la forme

for (i = 0; ; ++i ) {
if ( f(i) == 0 ) return;
}

Je le donne à H, qui rien qu'en le lisant me dit, "ce programme s'arrête ou ne s'arrête pas", alors je sais si ma proposition logique est vraie ou fausse.

L'article de Turing sur le halting problem et l'article de Goedel quelques années avant, ont mis fin à l'idée d'Hilbert d'une mathématique complètement débarassée de toute sémantique et ne manipulant que des symboles.

[inviteb7bc207b]

Dans une discussion du type "le réel est il calculable?", je trouve parfaitement normal de discuter des limites de la calculabilité.

Je suis aussi d'accord et cette limite est indiscutable. Mais ce qui m'intéresse en fait c'est pour le reste des problèmes: peuvent-ils être résolus par ordinateur ?

[inviteb7bc207b]

Ce n'est pas forcemment un problème trivial.
Si un programme H décidant de l'arrêt de n'importe quel programme P existait, je pourrais résoudre n'importe quelle question d'arithmétique.

Imaginons une proposition du type
"Il existe i tel que f(i)=0"

Cette proposition peut être quelque chose du genre
"il existe i > 1 tel que i et i +2 sont premiers", où n'importe quelle autre conjecture arithmétique encore non résolue à ce jour.

Si j'ecris un programme de la forme

for (i = 0; ; ++i ) {
if ( f(i) == 0 ) return;
}

Je le donne à H, qui rien qu'en le lisant me dit, "ce programme s'arrête ou ne s'arrête pas", alors je sais si ma proposition logique est vraie ou fausse.

Je parle des programmes dans la vraie vie.