Alors justement (et j'en profite pour vous remercier de vos explications), d'après ce que j'ai compris, ce problème de halting est un cas typique du théorème d'incomplétude de gödel dans le contexte d'une machine de turing (c'était avec cet exemple que j'avais compris ce théorème).
C'est un cas d'indécidabilité au sein d'une machine de turing (son cadre formel plus exactement), mais peut-on lever cette indécibilité dans un sur-ensemble d'une machine de turing ?
Je suppose que c'est l'objet de pas mal de recherche ?
(et qu'il me semble qu'un ordinateur quantique est un sur ensemble d'une machine de turing).
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
[^] # Re: Halting problem
Posté par Ontologia (site web personnel) . En réponse au journal Déterminer le domaine d'un programme. Évalué à 2.
C'est un cas d'indécidabilité au sein d'une machine de turing (son cadre formel plus exactement), mais peut-on lever cette indécibilité dans un sur-ensemble d'une machine de turing ?
Je suppose que c'est l'objet de pas mal de recherche ?
(et qu'il me semble qu'un ordinateur quantique est un sur ensemble d'une machine de turing).
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker