Qu’est-ce que la machine à poster, expliquez-la avec un exemple ?
Une machine Post est encore un autre reconnaisseur ou accepteur de langage. Comme nous les avons définis , les machines Post sont déterministes, c’est-à-dire que pour chaque chaîne d’entrée, il n’y a qu’un seul chemin à travers la machine ; nous n’avons aucune alternative à aucun moment.
Pourquoi une machine de Turing ne peut-elle pas résoudre le problème de l’arrêt ?
Turing a prouvé qu’il n’existe aucun algorithme qui décide toujours correctement si, pour un programme et une entrée arbitraires donnés, le programme s’arrête lorsqu’il est exécuté avec cette entrée. L’essence de la preuve de Turing est qu’un tel algorithme peut être amené à se contredire et ne peut donc pas être correct.
Une machine de Turing ne peut-elle pas s’arrêter ?
Machine de Turing – La machine de Turing peut s’arrêter ou non et cela dépend de l’algorithme et de l’entrée associée à l’algorithme.
Qu’est-ce qu’un problème de correspondance Post, illustrez-le par un exemple ?
Post Correspondence Problem est un problème indécidable populaire qui a été introduit par Emil Leon Post en 1946. Il est plus simple que Halting Problem . Dans ce problème, nous avons un nombre N de Dominos (tuiles). Le but est d’organiser les tuiles dans un ordre tel que la chaîne créée par les numérateurs soit la même que la chaîne créée par les dénominateurs.
Quelles sont les conséquences d’un problème d’arrêt?
Si nous nous référons au problème d’arrêt des machines de Turing, cela signifierait que nous ne pouvons décider de la cohérence que des systèmes axiomatiques d’aujourd’hui. Autrement dit, les mathématiques pourraient évoluer radicalement si un algorithme résolvant le problème d’arrêt des machines de Turing était inventé.