La mise en œuvre concrète d'une machine de Turing est réalisée avec les éléments suivants :
1. Un « ruban » divisé en cases consécutives. Chaque case contient un symbole parmi un alphabet fini. L'alphabet contient un symbole spécial « blanc » ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est supposé être de longueur infinie vers la gauche ou vers la droite, en d'autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases non encore écrites du ruban contiennent le symbole « blanc ».
2. Une « tête de lecture/écriture » qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban.
3. Un « registre d'état » qui mémorise l'état courant de la machine de Turing. Le nombre d'états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l'état initial de la machine avant son exécution.
4. Une « table d'actions » qui indique à la machine quel symbole écrire, comment déplacer la tête de lecture ('G' pour une case vers la gauche, 'D' pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l'état courant de la machine. Si aucune action n'existe pour une combinaison donnée d'un symbole lu et d'un état courant, la machine s'arrête.
Un programme est un ensemble de symbole écrit sur la bande, les données initialises sont aussi des symboles écrit sur la bande (par exemple préfixant le programme).
La fonction halt dont on parle depuis le début a étét discutée en pseudo-code (on aurait pû l'écrire en chinois que ça change rien)... on se fout de son implémentation (dans tous tes exemples tu présuposses que halt éxécute le programme reçu en argument... alors que rien ne l'y oblige ou pas, on s'en fout c'est son implémentation interne et nous on veut savoir si une telle fonction existe.) Or comme la démonstration montre qu'une telle fonction n'existe pas, ça n'a aucun sens de parler d'une éventuelle implémentation dans un éventuel langage. Pourquoi mettre ton halt(halt(halt(....)))). Pourquoi halt exécuterait donc le prog reçu en paramètre ? la spécification c'est de savoir pour tel programme et tel état initial est-ce que le programme s'arrête après un nombre fini d'étape ou non ? Et bien non, on ne peux pas... halt est impossible a écrire, il n'existe aucun algorithme qui pour un programme et un état initial de celui-ci puisse te dire si il s'arrêtera après un nombre fini d'étape.
Si maintenant tu n'as toujours pas compris, je pense que l'explication t'échappera pour toujours.
[^] # Re: Halting problem
Posté par allcolor . En réponse au journal Déterminer le domaine d'un programme. Évalué à 2.
Définition [modifier]
La mise en œuvre concrète d'une machine de Turing est réalisée avec les éléments suivants :
1. Un « ruban » divisé en cases consécutives. Chaque case contient un symbole parmi un alphabet fini. L'alphabet contient un symbole spécial « blanc » ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est supposé être de longueur infinie vers la gauche ou vers la droite, en d'autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases non encore écrites du ruban contiennent le symbole « blanc ».
2. Une « tête de lecture/écriture » qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban.
3. Un « registre d'état » qui mémorise l'état courant de la machine de Turing. Le nombre d'états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l'état initial de la machine avant son exécution.
4. Une « table d'actions » qui indique à la machine quel symbole écrire, comment déplacer la tête de lecture ('G' pour une case vers la gauche, 'D' pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l'état courant de la machine. Si aucune action n'existe pour une combinaison donnée d'un symbole lu et d'un état courant, la machine s'arrête.
Un programme est un ensemble de symbole écrit sur la bande, les données initialises sont aussi des symboles écrit sur la bande (par exemple préfixant le programme).
La fonction halt dont on parle depuis le début a étét discutée en pseudo-code (on aurait pû l'écrire en chinois que ça change rien)... on se fout de son implémentation (dans tous tes exemples tu présuposses que halt éxécute le programme reçu en argument... alors que rien ne l'y oblige ou pas, on s'en fout c'est son implémentation interne et nous on veut savoir si une telle fonction existe.) Or comme la démonstration montre qu'une telle fonction n'existe pas, ça n'a aucun sens de parler d'une éventuelle implémentation dans un éventuel langage. Pourquoi mettre ton halt(halt(halt(....)))). Pourquoi halt exécuterait donc le prog reçu en paramètre ? la spécification c'est de savoir pour tel programme et tel état initial est-ce que le programme s'arrête après un nombre fini d'étape ou non ? Et bien non, on ne peux pas... halt est impossible a écrire, il n'existe aucun algorithme qui pour un programme et un état initial de celui-ci puisse te dire si il s'arrêtera après un nombre fini d'étape.
Si maintenant tu n'as toujours pas compris, je pense que l'explication t'échappera pour toujours.