Bonjour,
J'ouvre cette discussion à la suite de "L'intelligence artificielle peut-elle se révéler néfaste ?". Le fil avait pas mal dévié de la question initiale et nous en étions arrivés à nous demander s'il existait des nombres qui ne soient pas calculables par une machine de turing, ou même des problèmes qui ne soient pas solvables par des programmes ?
La réponse à la question existe t il des problèmes qui ne soient pas solvables par des programmes est oui.
Un exemple : supposons que l'on ait écrit un programme P qui doit résoudre un problème donné, une question naturelle est : est ce que mon programme va donner la (une) solution en un temps fini ou est ce qu'il va se mettre à tourner sans jamais s'arreter (et donc ne jamais donner de solution)?
En bon informaticien on se dit qu'il suffit d'écrire un programme V qui aura comme fonction d'examiner un autre programme qu'on lui donne en entrée et qui répondra soit : oui le programme P que j'examine finira par s'arreter, soit non votre programme P tournera sans arret.
Et bien en fait ce n'est pas une bonne idée, on a montré qu'il est impossible d'écrire le programme V : Il n'existe pas de programme capable de determiner si un autre programme va ou non s'arreter.
Je propose donc la première réponse.
Turing a écrit son article fondateur sur les machines de turing pour formaliser la notion d'algorithme. Il ramène un traitement algoritmique a l'execution d'un automate composé d'un ruban infini et d'une tête de lecture qui peut écrire et lire sur le ruban. Il énonce alors sa thèse "Tout algorithme peut être formulé sous la forme d'une machine de Turing".
Cette énoncé est souvent considéré à tort, et est interprété comme si "Les machines de Turing pouvaient tout résoudre". Je cite par exemple Argyre dans le fil "L'intelligence artificielle est - elle néfaste".
C'est faux ! Dans le même article où Turing définit sa fameuse machine, il montre que les machines de Turing ne peuvent pas résoudre n'importe quel problème.Envoyé par Argyre
Pour sa démonstration, il considère le problème de l'arrêt d'une machine de Turing : Est - il possible de définir une machine de Turing capable de décider si une autre machine de Turing quelconque va s'arrêter ou non. En des termes plus modernes : est - il possible d'écrire un programme capable de déterminer si un programme quelconque s'arrête ou non ?
En procédant par un raisonnement par l'absurde il démontre que non ! J'avais fait une démo simplifiée là http://forums.futura-sciences.com/post254762-20.html .
Turing conclut alors que si la thèse de Church-Turing est juste alors il existe des problèmes qui ne sont pas solvables par des algorithmes.
On peut même montré qu'il existe des nombres qui ne sont pas calculables par un algorithme. Chaitin en a exhibé un : http://mathworld.wolfram.com/ChaitinsConstant.html .
La démonstration de la non - calculabilité de ce nombre est très simple : pour le connaitre il faut connaitre la probabilité qu'un programme de longueur N s'arrête, il faut donc un algorithme capable de statuer si un programme quelconque s'arrête ou non. Or ce programme n'existe, donc le nombre de Chaitin n'est pas calculable. Les matheux disent 'Que le nombre de Chaitin est définissable mais pas calculable'. Attention, ça n'empêche pas d'en faire une estimation en utilisant des moyens empiriques (voir la fin de la page http://mathworld.wolfram.com/ChaitinsConstant.html).
Donc effectivement pour répondre à Argyre : Voici un exemple où des numériciens (pas des physiciens) peuvent prédire un résultat alors qu'une machine de Turing en est incapable.
Croisement avec Erik qui m'a damé le pion
Il y a quelque chose qui m'échappe un peu dans ce fait. Est-ce que cette impossibilité est liée au caractère infini de la "bande" de la machine de turing ?
Dans le cas contraire je ne comprends pas le truc. Et en l'occurence, pour un programme qui tourne sur un pc (ou, donc, tout est fini), il me semble absolument évident qu'il est possible de faire un algorithme qui dit si un algorithme donné va s'arréter ou non sur une machine A (mais sur une machine B beaucoup plus puissante que A).
...c'est dire combien je dois être à coté de la plaque
Pour la démonstration simplifiée que tu donnes dans l'autre fil, il y a aussi un truc qui m'échappe. Pour commencer, pourquoi dans la boucle, on appelle halt(p,p) plutôt que halt(p) ? Je ne comprends pas ce qu'est sensée renvoyer l'hypothétique fonction halt() quand on lui envoie deux paramètres.
Ensuite, pour ce qui est de la démo en elle-même, je comprends pas tout non plus : si s est la chaine correspondant à boucle_si_halt, contient-elle le paramètre qu'on lui envoie ? Parce qu'au dela de l'algorithme en lui-même, c'est (surtout dans le cas présent) principalement la valeur du paramètre envoyé qui va déterminer si l'algorithme s'arrete ou pas. Or s ne peut pas contenir son algorithme et elle-même ...???
C'est tout à ton honneur car ce n'est absolument pas intuitif. Non ce n'est pas lié au caractère infini de la bande.Il y a quelque chose qui m'échappe un peu dans ce fait. Est-ce que cette impossibilité est liée au caractère infini de la "bande" de la machine de turing ?
Dans le cas contraire je ne comprends pas le truc. Et en l'occurence, pour un programme qui tourne sur un pc (ou, donc, tout est fini), il me semble absolument évident qu'il est possible de faire un algorithme qui dit si un algorithme donné va s'arréter ou non sur une machine A (mais sur une machine B beaucoup plus puissante que A).
...c'est dire combien je dois être à coté de la plaque
C'est une erreur de ma part, il faut bien lire halt(p) et pas halt(p,p).Pour la démonstration simplifiée que tu donnes dans l'autre fil, il y a aussi un truc qui m'échappe. Pour commencer, pourquoi dans la boucle, on appelle halt(p,p) plutôt que halt(p) ? Je ne comprends pas ce qu'est sensée renvoyer l'hypothétique fonction halt() quand on lui envoie deux paramètres.
S est la succession de caractères correspondant au programme boucle_si_halt : rien ne t'empêche d'appliquer boucle_si_halt sur S.Ensuite, pour ce qui est de la démo en elle-même, je comprends pas tout non plus : si s est la chaine correspondant à boucle_si_halt, contient-elle le paramètre qu'on lui envoie ? Parce qu'au dela de l'algorithme en lui-même, c'est (surtout dans le cas présent) principalement la valeur du paramètre envoyé qui va déterminer si l'algorithme s'arrete ou pas. Or s ne peut pas contenir son algorithme et elle-même ...???
La contradiction vient du fait que tu appliques le programme à lui même.
C'est du même type que la paradoxe des ensembles qui ne s'appartiennent pas d'Husserl ou du menteur de Parménide :tu fabriques un énoncé contradictoire en prenant un élément qui se définit en se référant à lui-même.
Dernière modification par spi100 ; 09/09/2005 à 14h05.
Que de prose pour arriver à une conclusion que Gödel a démontré depuis longtemps. Il y a manifestement un problème de compréhension entre nous, car je suis tout à fait d'accord avec toi sur ce point !
Il est mille fois prouvé que les ordinateurs ne peuvent résoudre tous les problèmes. Là n'est pas la bonne question et je vais donc sortir de ce fil de discussion et en proposer un autre avec la bonne question : existe t-il des problèmes comportant une solution mathématique ou physique qui ne peuvent être résolus de façon algorithmique ? Dit autrement : les ordinateurs peuvent-ils résoudre tous les problèmes SOLVABLES !
Le calcul du nombre de Chaitin ne te suffit pas comme exemple ?
C'est bien là que je pige pas : un programme, il lui faut des paramètres pour tourner. Quand je passe à la fonction halt() un programme pipo(entier a, entier b) pour savoir s'il va s'arréter, il faut bien que je lui donne aussi les paramètres a et b que je lui envoie... Et donc c'est donc exactement la même chose avec boucle_si_halt : ses paramètres, ce sont un programme et les paramètres qu'on lui passe.
Si la fonction halt() pouvait exister, on pourrait donc sans problème appeler boucle_halt(fonction1(a,b,c)), et du coup appeler boucle_halt(boucle_halt(foncti on1(a,b,c))). Mais pour moi, appeler boucle_halt sur elle-même ne veut tout simplement rien dire. Mais je ne vois absolument pas en quoi cela permet de démontrer la non-existence de cette fonction.
De la même manière, on ne peut pas construire un fichier zip qui se contienne lui-même, mais on peut faire un zip avec n'importe quel fichier, et faire un zip de ce zip, et ainsi de suite. Ca ne change absolument rien au fait qu'il existe un programme winzip qui permet de mettre n'importe quel type de fichier dans un zip... ou est la différence ?
Peut-être que ça sera plus facile de me coller le nez sur mon erreur si je prends le problème dans l'autre sens : Si une machine de turing a un nombre d'états finis, il suffit de simuler son execution pas à pas en regardant à chaque étape l'état de la machine. Si on retrouve à un moment donné un état déjà trouvé pendant l'exécution du programme, le reste se déroulera exactement de la même manière et le programme ne s'arrètera jamais. Si par contre on sort du programme, on a aussi la réponse. Comme il n'existe pas un nombre infini d'états possibles, on saura si le programme se termine, et en un temps fini. Argh... me voilà en train de démontrer des trucs faux... bon, il y a nécessairement un truc énorme dans ce que je viens de dire, mais j'arrive pas à voir quoi...
Certainement pas, car personne ne peut prétendre pouvoir calculer ce nombre qui comporte un nombre infini de décimales.
C'est un problème que personne ne peut résoudre, ni humain ni machine, il est donc hors-sujet.
Pi est il calculable pour toi ? Voilà aussi un nombre qui comporte un nombre infini de décimales et qui est pourtant calculable au sens de la calculabilité.
Disons qu'il est calculable en théorie si on disposait d'un temps infini, mais il n'est pas calculable expérimentalement.
D'où le terme solvable (euh... plutôt soluble au fait, non ?) qui rajoute un côté pragmatique à la notion de calculabilité.
Alors si tu préfères je pose le problème de cette façon :
Problème solvable : "Peux t'on calculer avec un algorithme, pi avec une précision arbitrairement petite ?"
Oui.
"Peut - on calculer avec un algorithme le nombre de Chaitin, avec une précision arbitrairement petite ?"
Non
Tu remarqueras que le problème posé n'est pas d'écrire dans sa totalitéou
Yat,
C'est peu être le mécanisme de la démonstration qui te gêne. Regarde celle là http://forums.futura-sciences.com/post256046-22.html ce n'est pas sur le même sujet mais elle utilise exactement le même mécanisme que celle de Turing.
Oui, je comprends bien l'exemple donné, il est effectivement très simple. Mais pour le problème de la machine de turing, ça ne se passe pas de la même manière : c'est le fait même d'appliquer le programme boucle_halt() sur lui-même qui n'a pas de sens, pour moi. En effet, appeler boucle_halt() sans argument n'a aucun sens. Avant de se poser la moindre question sur son comportement, il faut d'abord préciser ce qu'on lui donne en paramètre.
Enfin, ça, ça ne fait qu'embrouiller encore un peu plus les choses dans ma tête. Le fait est que je ne vois toujours pas en quoi ça prouve que halt() ne peut pas exister : J'ai l'impression qu'on peut faire exactement le même raisonnement pour une fonction un peu différente :
Alors que retour(), y a pas de problème, elle existe. En quoi cette démonstration diffère de celle sur la fonction qui dit si un programme s'arrète ? Ca m'inquiète, ça... si je peux pas comprendre un truc qui est manifestement aussi évident, je n'ai plus qu'à aller là ou je dois être :
Peu importe si oui ou non on peut ou pas calculer quelque chose avec un algorithme, le problème est de trouver quelque chose non calculable par un algorithme et calculable par un autre moyen (expérimental, pas théorique), sans être obligé de faire référence à un infini temporel, spatial, ou une continuité de la matière espace-temps.
Pourtant c'est bien le coeur du problème et je ne vois pas en quoi la définition de la calcubilité d'un nombre fait référence a "un infini temporel" ou "une contuinité de la matière espace temps" ? Mais si tu veux un autre exemple :
- donner une séquence de nombres complètement aléatoire : un algorithme ne le peut pas, mais tu peux utiliser un phénomène physique comme une désexitation radioactive.
Dernière modification par spi100 ; 09/09/2005 à 18h05.
Non ton exemple ne marche pas car on ne sait pas ce que doit faire la fonction retour(), elle n'est pas spécifiée.
Dans le cas du 'halting problem', la fonction halt est parfaitement spécifiée mais n'est pas implémentable.
Est - ce que tu es plutot programmeur ou matheux ? Je peux te proposer d'étayer un peu plus mais je ne sais pas si tu préfères que je me lance dans une démo plus abstraite ou dans un exemple plus concret.
Ta démonstration est tout à fait juste... si une machine de Turing a un nombre d'états finis!Si une machine de turing a un nombre d'états finis, il suffit de simuler son execution pas à pas en regardant à chaque étape l'état de la machine. Si on retrouve à un moment donné un état déjà trouvé pendant l'exécution du programme, le reste se déroulera exactement de la même manière et le programme ne s'arrètera jamais. Si par contre on sort du programme, on a aussi la réponse. Comme il n'existe pas un nombre infini d'états possibles, on saura si le programme se termine, et en un temps fini. Argh... me voilà en train de démontrer des trucs faux
Or par définition, il est toujours possible de rallonger la mémoire d'une machine de Turing! Il y a donc bien un infini qui se cache ici.
Bah si, qu'elle est spécifiée : "programme retour() capable de déterminer si un programme P qui s'arrete en renvoyant une valeur booléenne renvoie vrai.". Bon, ici on mélange un peu les fonctions et programmes, mais ça donnerait fondamentalement un truc dans le genre :
BOOL retour (fonction P)
{
return (P());
}
retour
C'est rien du tout... après, si la fonction f prend des arguments, il faudra juste les passer aussi à la fonction retour(). Bon, mis à part le fait qu'il faut faire intervenir un pointeur sur fonction, ce qu'on ne voit pas forcément à sa première lecon de programmation, c'est quand même difficile de trouver plus bateau, comme fonction.
Bah pour le moment disons plutôt programmeur, et disons plutôt exemple concret. Merci de tes efforts, en tout cas ! C'est pas toujours évident de faire rentrer quelque chose dans ma tête de bois...
Oui, c'est bien la seule limitation que je vois, comme précisé dans mon post 5. Mais spi100 a l'air de dire que l'impossibilité ne vient pas de là. C'est ça qui me gène. Si par contre l'impossibilité ne vient que du caractère infini de la bande, alors là ça ne me pose plus le moindre problème.Ta démonstration est tout à fait juste... si une machine de Turing a un nombre d'états finis!
Or par définition, il est toujours possible de rallonger la mémoire d'une machine de Turing! Il y a donc bien un infini qui se cache ici.
Parce qu'avec une bande infinie, il est évident qu'on ne peut pas faire grand chose. Mais du coup, concrêtement, comme un ordinateur a un nombre d'états finis, il suffit d'une deuxième machine suffisamment grosse (capable d'émuler intégralement l'ordinateur de départ, et de garder en mémoire plusieurs copies complêtes de son état) pour déterminer si un programme donné va s'arréter ou pas sur la première machine.
Alors qu'en est-il ? C'est l'infini qui fout la merde et la phrase "il est impossible de faire un programme qui calcule si un programme donné se termine ou part en boucle" n'est vraie que dans une situation idéale avec une machine à mémoire infinie, ou bien il y a un autre truc qui empêche la chose et j'ai toujours rien compris ?ou
Salut,
Yat j'essaierai de te sortir quelque chose ce soir. Pour l'histoire de bande infini, c'est indispensable si tu veux pouvoir affirmer qu'il est possible d'executer n'importe quel programme sur ta machine de Turing. Sinon, il y a bien sûr des programmes que tu ne pourras pas executer faute de mémoire, et certains programmes partant dans une boucle infini finiront par s'arreter faute de mémoire, ceci indépendemment de l'algo.
Bon allez je m'y colle. Attention je ne suis pas un spécialiste, j'essaie juste d'expliquer ce que j'en ai compris. Plutot que de passer par l'écriture d'un programme, je vais essayer de discuter en termes de machines de Turing, peut être que ça te paraitra plus clair comme ça.
machine de turing
Il s'agit d'un ruban découpé en cases, le nombre de cases est infini. Une tête de lecture / ecriture peut lire et écrire des symboles
Plus formellement la définition d'une machine de Turing est un ensemble de quintuplets de la forme :
Avant le démarrage de la machine de Turing, on peut écrire une succession de symboles sur le ruban, puis démarrer la machine au début de la chaine de symboles.
L'ensemble des Regles constituent l'algorithme, et la chaîne initiale de symboles constitue les paramètres passés à l'algorithme.
quelques résultats remarquables
Tout algorithme peut être représenté sous la forme d'une machine de Turing. C'est la thèse de Church-Turing.
On démontre qu'il existe une bijection entre l'ensemble des entiers naturels et l'ensemble des machines de Turing. En d'autres termes, on peut caractériser de façon univoque une machine de Turing par la donnée d'un nombre entier. Pour la suite, on parlera donc de la machine K (avec K entier) pour parler d'une machine de Turing en particulier.
Il existe une machine de Turing Universel, qui permet d'émuler n'importe quel machine de Turing. Il suffit de considérer une machine de Turing dont on divise le ruban en deux parties, l'une des parties recevant la définition d'une machine de Turing particulière. Or comme une machine de turing est entièrement définie par la donnée d'un nombre entier, il suffit donc décrire ce nombre sur le ruban ( en suite de 0 et de 1 par exemple). Plusieurs formes explicites de cette machine Universelle ont été données, la plus concise a été donnée par le grand Feynman en personne.
On voit donc que la machine de Turing peut prendre deux formes équivalentes:
La forme d'un automate.
Ou d'un symbole et en particulier un entier numérique.
Le paradoxe du halting problem s'appuie sur cette dualité symbole-automate.
Le halting problem
On cherche donc à définir une machine de Turing H (H un entier), tel que si j'écris initialement sur le ruban, la définition d'une machine de Turing K quelconque (l'ecriture d'un simple nombre entier K suffit) alors après execution, la machine doit finir en écrivant un symbole
Suppons que la machine H existe, je peux construire une nouvelle machine P implémentant l'algorithme suivant :
Le ruban de la machine H étant initialisé avec la chaîne représentant le nombre K (et donc aussi la machine de Turing K),
Si H donne
Si H donne
Que se passe t'il alors si K = P ?
Si P s'arrête, H doit donner
Si H donne
Donc les machines P et H n'existent pas.
Joli
Un truc m'a toujours gratouillé avec cette démonstration: ok une machine de Turing prédisant l'arrêt de n'importe quel autre machine de Turing est impossible, mais est-ce que ça exclue l'existence de classes de machine de Turing qui seraient chacune capable de prédire l'arrêt de sous-ensembles parmi toutes les machines de Turing possibles?
J'imagine que pour s'attaquer à cette démonstration, il faudrait partir de l'idée que si une classe de machine de Turing est calculable, alors ça équivaut à une seule machine, mais je ne vois pas trop comment gérer la suite... Une idée quelqu'un?
Tu n'es peut-être pas un spécialiste, mais au moins les choses sont claires dans ta tête et tu les rends claires sur le papier... euh, l'écran.
Mais ...
...bon, pour les deux premiers paragraphes, c'est maintenant limpide. Donc la machine de Turing, définie par un ensemble de rêgles (que l'on peut résumer à un seul entier), fait défiler un ruban dans un sens ou dans un autre, en lisant ou écrivant des données dessus, le tout en fonction de son ensemble de rêgles.
Donc on est bien d'accord sur le fait qu'un entier peut définir intégralement une machine de turing. Mais () son comportement (et en particulier, le fait qu'il s'arrète au bout d'un temps fini ou pas) dépend également du contenu initial du ruban qu'on lui donne. Maintenant que je pense avoir bien compris le truc, je peux essayer de donner un exemple. Je définis une machine ainsi :
(etat initial, symbole lu, symbole écrit, mouvement, nouvel état)
e1, 1, 0, D, e2
e1, 0, 1, D, e2
e2, 1, 1, G, e1
l'état initial étant e1
Si la deuxième case du ruban contient le symbole 1, la machine change le symbole de la première case, passe à la deuxième et à l'état e2, puis lit un 1, écrit un 1 (donc, n'écrit rien), puis repasse dans l'état e1 sur la première case, et recommence indéfiniment.
Si la deuxième case du ruban contient le symbole 0, la machine va changer l'état de la première case, passer à la deuxième et à l'état e2, et là lira un 0 et s'arrètera.
J'ai donc toujours le même problème avec la suite :Ce qui ne me va pas à ce stade là du récit, c'est que telle que tu la définis, la machine H n'a pas suffisamment d'éléments pour donner sa réponse. Il manque un paramètre. Par exemple, si K est la machine que je définis plus haut, il faut connaitre la valeur de la deuxième case du ruban pour savoir si elle va s'arréter ou pas. Donc, sans avoir besoin de pousser plus loin le raisonnement par l'absurde, je peux d'ores et déjà comprendre qu'une telle machine n'existe pas, mais ça ne fait pas avancer le schmilblick, puisque dans ce cas rien que le fait de se poser la question de savoir si la machine s'arrète ou boucle n'a aucun sens si on ne précise pas les paramètres.Le halting problem
On cherche donc à définir une machine de Turing H (H un entier), tel que si j'écris initialement sur le ruban, la définition d'une machine de Turing K quelconque (l'ecriture d'un simple nombre entier K suffit) alors après execution, la machine doit finir en écrivant un symbole
Pour que la question ait un sens (ou, plus précisément, pour que je la comprenne), il faut donc considérer la machine H de la même manière que la machine universelle que tu décris plus haut : une partie du ruban contient la définition de la machine K, et l'autre contient le contenu du ruban qu'on envoie à la machine K. Pour shématiser, le ruban que l'on donne à H pourra s'écrire K+R, ou le symbole + représente la concaténation, et R le ruban passé à K.
Cette machine P (tout comme H) ne doit donc, selon moi, pas avoir son ruban initialisé à K, mais à K+R.Suppons que la machine H existe, je peux construire une nouvelle machine P implémentant l'algorithme suivant :
Le ruban de la machine H étant initialisé avec la chaîne représentant le nombre K (et donc aussi la machine de Turing K),
Si H donne
Si H donneCelà dépend tout naturellement de la valeur de R. La machine P va simplement prendre en entrée un ruban indiquant P+R, en sachant que R est lui-même un ruban de la forme K+R2, ou K est la définition d'une machine de turing, et R2 le ruban qu'on lui donne. Il est donc normal que, si la machine K s'arrète au bout d'un temps fini quand on lui donne le ruban R2, la machine P parte en boucle infinie quand on lui donne le ruban R. Du coup, elle s'arrètera au bout d'un temps fini si on lui donne le ruban P+R. Et si on lui donne P+P+R, elle partira en boucle. Et ainsi de suite.
Pour moi il ne s'agit tout bêtement que d'un appel récursif sans cas terminal, et ne remettant absolument pas en cause l'existence de la machine P, ni celle de H. Comme je l'ai déjà signalé dans un post précédent, ce raisonnement peut s'appliquer à la lettre pour démontrer qu'il n'existe pas de fonction renvoyant le résultat d'une autre fonction. Pourtant cette fonction existe, elle est même triviale. Alors ou est cette différence que je ne vois pas ?
A mon avis il n'est pas nécessaire d'entrer autant dans le détail pour me faire comprendre ou je me plante... le truc doit être énorme, juste devant mes yeux, mais comme dirait l'autre, il n'est de pire aveugle que celui qui ne veut pas voir. J'apprécie tes efforts, mais faudrait pas que ça devienne de l'acharnement térapeuthique
Désolé Yat, mais comme je le disais plus haut, je suis loin d'être un expert et je ne vois pas ce qui cloche dans ton raisonnement.
Jiav,
A cette page http://en.wikipedia.org/wiki/Halting_problem (dans la section "Recognizing partial solutions"), il y a quelque chose sur les machines de turing permettant de résoudre partiellement le halting problem. Je n'ai pas encore compris l'argumentaire mais la conclusion est vraiment contre-intuitive
This problem sounds like it might be easier than the halting problem itself. It is not. It is just as undecidable as the halting problem
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.
spi100 => merci, je suis en train de voir ça
Si je comprend bien, il existe des machines résolvant partiellement (sur des sous-ensembles de toutes les machines de Turing possibles) le halting problem, mais il est impossible d'avoir une machine de Turing qui dans tous les cas dit si une machine particulière peut résoudre partiellement le problème.y a quelque chose sur les machines de turing permettant de résoudre partiellement le halting problem
On retombe encore sur cet infini.. et donc sur ma question en la modifiant un peu: on sait qu'il existe des machines de Turing qui résolvent le halting problem sur des sous-ensembles de machines de Turing. On sait qu'il n'est pas possible de savoir si ces machines marchent à tous coup. Mais est-ce qu'on peut avoir une méthode nous disant, sous certaines limites, qu'elles peuvent marcher?
... pas très clair mon truc
Une méthode probablement mais a priori pas algorithmique. J'imagine que les auteurs qui ont cherché à calculer le nombre de Chaitin ont du utiliser ce type de méthodes pour calculer la probabilité qu'un algorithme s'arrête en fonction de sa longueur.
Sur cette page http://mathworld.wolfram.com/ChaitinsConstant.html
ils citent par exemple Calude et al. (2002) mais je n'ai pas trouvé le papier correspondant.
Suffisait de taper le titre dans google
http://www.expmath.org/expmath/volum...ude361_370.pdf
Bon reste plus qu'à le lire
