Problème d'arrêt de la machine de Turing

Input - Une machine de Turing et une chaîne d'entrée w.

Problem - La machine de Turing termine-t-elle le calcul de la corde wen un nombre fini d'étapes? La réponse doit être oui ou non.

Proof- Dans un premier temps, nous supposerons qu'une telle machine de Turing existe pour résoudre ce problème et ensuite nous montrerons qu'elle se contredit. Nous appellerons cette machine de Turing unHalting machinequi produit un «oui» ou un «non» dans un laps de temps limité. Si la machine à l'arrêt se termine dans un laps de temps limité, la sortie est «oui», sinon par «non». Ce qui suit est le schéma de principe d'une machine d'arrêt -

Maintenant, nous allons concevoir un inverted halting machine (HM)’ comme -

• Si H renvoie OUI, puis boucle indéfiniment.

• Si H renvoie NON, puis arrêtez.

Voici le schéma de principe d'une `` machine d'arrêt inversée '' -

De plus, une machine (HM)₂ quelle entrée elle-même est construite comme suit -

• Si (HM) ₂ s'arrête sur l'entrée, boucle indéfiniment.
• Sinon, arrêtez.

Ici, nous avons une contradiction. Par conséquent, le problème de l'arrêt estundecidable.