problème de l’arrêt \pʁɔ.blɛm.də.l‿a.ʁɛ\ (locution nominale) : Problème de décision consistant à déterminer, à partir de la description d’un programme informatique et d’une entrée, si l’exécution de ce programme sur cette entrée se termine à l’issue d’un nombre fini d’étapes ou se poursuit indéfiniment.
Synonymes de problème de l’arrêt
problème de l’arrêt d’une machine de Turing· halting problem
Définitions
Locution nominale \pʁɔ.blɛm.də.l‿a.ʁɛ\
- Problème de décision consistant à déterminer, à partir de la description d’un programme informatique et d’une entrée, si l’exécution de ce programme sur cette entrée se termine à l’issue d’un nombre fini d’étapes ou se poursuit indéfiniment.Le problème de l’arrêt est en théorie décidable dans le cas d’une mémoire de taille finie, car l’ensemble des états de la mémoire, bien que très grand, est fini lui-même.
Étymologie
Locution composée de problème et de arrêt, cette dernière acception étant un calque sémantique de l’anglais halting, dans halting problem, expression employée par le mathématicien et cryptologue britannique Alan Mathison Turing dans son article fondateur relatif à la décidabilité des fonctions calculables, « On Computable Numbers, with an Application to the Entscheidungsproblem » (La machine de Tu…
Mots voisins
probe· probes· probité· problématique· problématiquement· problème· problémisme· proboscide· proboscidien· proboscis· probritannique· procaïne
Sources
- « problème de l’arrêt », Wiktionnaire, le dictionnaire libre. Texte sous licence CC BY-SA 4.0.
Une erreur, un synonyme manquant ? Corrigez la page du Wiktionnaire : la prochaine mise à jour de Synonyma la reprendra.