INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q054 — Existe-t-il un algorithme général qui décide pour tout programme si celui-ci imprimera un jour la chaîne ‘LANXAS’ ? Justifier.
Non, il n’existe pas d’algorithme général qui décide, pour tout programme, s’il imprimera un jour la chaîne « LANXAS ». Cette impossibilité découle directement du théorème d’indécidabilité du problème de l’arrêt, établi par Alan Turing en 1936. Pour le justifier, supposons par l’absurde qu’un tel algorithme existe, et nommons-le P. Étant donné un programme quelconque, P répondrait « oui » si ce programme imprime un jour « LANXAS », et « non » dans le cas contraire. Considérons alors un programme quelconque M, dont on souhaite savoir s’il s’arrête. Construisons un programme M’ qui se comporte de la manière suivante : il exécute M, puis, si M s’arrête, il imprime « LANXAS » ; si M ne s’arrête jamais, il n’imprime jamais « LANXAS ». On obtient alors l’équivalence suivante : M’ imprime « LANXAS » si et seulement si M s’arrête. En effet, M’ n’imprime « LANXAS » qu’après l’arrêt de M, et il l’imprime dès que M s’arrête. Dès lors, appliquer P à M’ revient exactement à décider si M s’arrête. Autrement dit, P résoudrait le problème de l’arrêt pour tout programme M. Or le problème de l’arrêt est indécidable : aucun algorithme général ne peut décider si un programme quelconque s’arrête. Cette contradiction invalide l’hypothèse d’existence de P. Un tel algorithme général n’existe donc pas. Cette réduction fonctionne pour toute chaîne fixée, y compris « LANXAS », car la construction de M’ ne dépend pas du contenu de la chaîne. Le résultat vaut donc pour n’importe quelle chaîne de sortie donnée, et non seulement pour « LANXAS ». Ma confiance en cette réponse est de 98 pour cent, car il s’agit d’une déduction formelle classique, directement calquée sur la preuve canonique de l’indécidabilité du problème de l’arrêt par réduction. La seule marge réside dans la formulation, non dans le fond du raisonnement.
Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.