Tu oublis le cas du compilo C de l'interpréteur python qui exécute un script.
Pose bien ta question, c'est quoi le programme dont tu veux savoir si il s'arrête, et quelles sont ces données dans ce cas ? Tu peux toujours ramener ton problème à ce doublet.
Exemple : pour un compilo, ses données c'est les fichiers sources ou les fichiers objets. Il s'arrête sur une erreur ou en produisant en général du code objet.
Pour un interpréteur ses données c'est le code des fichiers du langage et éventuellement ses IOs. Il s'arrête pas si dans le code des fichiers du langage t'as un 'main(){ while(1){} ; }' ou équivalent par exemple. Il s'arrête si t'as 'main(){ return true; }' ou si t'as pas de main ou sur une erreur de syntaxe, ou sur une erreur d'IO, ...
Après pour nuancer, pour citer wp: The halting problem is, in theory if not in practice, decidable for linear bounded automata (LBAs), or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:
C'est décidable si t'as une mémoire finie et une machine déterministe, comme nos machine à nous. Après en pratique si il faut dérouler le programme et il faut sauvegarder tous ses états pour détecter si il revient pas sur un état qu'il a déja rencontrer et donc si il boucle, c'est pas pratiquement faisable.
[^] # Re: Halting problem
Posté par thoasm . En réponse au journal Déterminer le domaine d'un programme. Évalué à 2.
Tu oublis le cas du compilo C de l'interpréteur python qui exécute un script.
Pose bien ta question, c'est quoi le programme dont tu veux savoir si il s'arrête, et quelles sont ces données dans ce cas ? Tu peux toujours ramener ton problème à ce doublet.
Exemple : pour un compilo, ses données c'est les fichiers sources ou les fichiers objets. Il s'arrête sur une erreur ou en produisant en général du code objet.
Pour un interpréteur ses données c'est le code des fichiers du langage et éventuellement ses IOs. Il s'arrête pas si dans le code des fichiers du langage t'as un 'main(){ while(1){} ; }' ou équivalent par exemple. Il s'arrête si t'as 'main(){ return true; }' ou si t'as pas de main ou sur une erreur de syntaxe, ou sur une erreur d'IO, ...
Après pour nuancer, pour citer wp: The halting problem is, in theory if not in practice, decidable for linear bounded automata (LBAs), or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:
C'est décidable si t'as une mémoire finie et une machine déterministe, comme nos machine à nous. Après en pratique si il faut dérouler le programme et il faut sauvegarder tous ses états pour détecter si il revient pas sur un état qu'il a déja rencontrer et donc si il boucle, c'est pas pratiquement faisable.