Quel est le problème d’arrêt de la machine de Turing ?
Machine de Turing – Maintenant, discutons du problème d’ arrêt : Le problème d’arrêt – Étant donné qu’un programme/algorithme s’arrêtera ou non ? L’arrêt signifie que le programme sur une certaine entrée l’acceptera et l’ arrêtera ou le rejettera et s’arrêtera et il n’entrera jamais dans une boucle infinie. Fondamentalement , arrêter signifie mettre fin.
Le problème de l’arrêt peut-il être résolu en temps polynomial ?
Problème d’arrêt , P=NP ? … Un polynôme non déterministe – problème de temps complet (NP-complet) est un problème qui peut être résolu en temps polynomial sur une machine de Turing non déterministe, mais nécessite apparemment un temps exponentiel sur une machine de Turing déterministe. Les problèmes qui nécessitent un temps exponentiel sont dits insolubles.
Comment prouver l’indécidabilité ?
Pour une preuve correcte, besoin d’un argument convaincant que la MT finit toujours par accepter ou rejeter toute entrée. Comment prouver qu’une langue est indécidable ? Pour prouver qu’un langage est indécidable , il faut montrer qu’il n’y a pas de machine de Turing qui puisse décider du langage. C’est difficile : cela nécessite de raisonner sur toutes les MT possibles.
Pourquoi l’ATM n’est-il pas décidable ?
Parce que nous savons que ATM est reconnaissable, notre théorème implique que ATM et ATM sont tous deux décidables . Mais nous savons que l’ ATM n’est pas décidable . C’est une contradiction, donc ATM ne peut pas être reconnaissable. Le langage ATM et son indécidabilité (y compris la preuve).
Quelles sont les deux choses que vous devez faire pour montrer qu’une langue est décidable ?
Comment prouver que le langage est décidable ? [dupliquer]
- Si M accepte w alors U accepte.
- Si M a rejeté w alors U rejette.
- Si i ≥n alors U rejette.