halt est l'algorithme (générique) qui prends 2 paramètres, le programme, et un input et te dit si pour ce programme et cette entrée ce programme s'arrête. Le fait est que cet algorithme est générique (ie, c'est un algorithme qui s'arrête toujours, donc qui donne toujours une solution en un temps fini) La démonstration, montre qu'un tel algorithme n'existe pas, car si c'était le cas, cela amène à une contradication.
Un problème est dit indécidable si il n'a pas de solution en un temps fini.
La page de wikipédia est bien faite je trouve et sans aucune erreur.
[^] # Re: Que ne savons-nous pas ?
Posté par allcolor . En réponse au journal Que ne savons-nous pas ?. Évalué à 1.
Un problème est dit indécidable si il n'a pas de solution en un temps fini.
La page de wikipédia est bien faite je trouve et sans aucune erreur.