# Synonymes de problème de l’arrêt

Source : https://synonyma.fr/probl%C3%A8me%20de%20l%E2%80%99arr%C3%AAt · 2 synonymes · 0 antonymes · mis à jour le 2026-11-03

## Synonymes de problème de l’arrêt

### Locution nominale

- problème de l’arrêt d’une machine de Turing, halting problem

## Définitions

### Locution nominale \pʁɔ.blɛm.də.l‿a.ʁɛ\

1. 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…

## Sources et licence

- Wiktionnaire, « problème de l’arrêt » : https://fr.wiktionary.org/wiki/probl%C3%A8me%20de%20l%E2%80%99arr%C3%AAt (CC BY-SA 4.0)