Machines et machines turation Schemas

Question

Arthur Dent, en utilisant la technologie de l'ère spatiale pas encore disponible sur la terre a développé un algorithme qui détermine si un M1 ou TM arrête pas quand a commencé sur une bande vierge. Mais plus tard, il a découvert que le sens à la vie, l'univers et tout est 42.

(a) [5] Étant donné une TM M2, prouver que Arthur peut déterminer si des arrêts M2 ou non sur l'entrée 42 en utilisant le programme qu'il a déjà développé qui détermine si une arrête TM M1 ou non au démarrage sur une cassette vierge. Si vous créez une nouvelle TM dans votre preuve, donner son schéma de la machine.

(b) [5] Supposons qu'il y ait un programme qui est plus rapide que celui de Arthur, mais il répond à la question de savoir si une arrête TM M2 sur l'entrée 42. Expliquer comment Arthur peut utiliser cet algorithme pour déterminer si certains arrêts TM M1 lors du démarrage sur une cassette vierge. Si vous créez une nouvelle TM dans votre preuve, donner son schéma de la machine.

(c) [5] Nous avons prouvé en classe que le problème de déterminer si un TM M arrête lors du démarrage sur une cassette vierge n'est pas décidable. Est-il partie (a) ou partie (b) qui peut être utilisé pour prouver qu'il est indécidable pour déterminer si un M sur TM arrête l'entrée 42?

aide quelqu'un peut me déchiffrer ce que mon prof parle ici?

Answer 1

Bienvenue à une théorie de la science informatique vraiment compliqué. Essayez de commencer ici: http://en.wikipedia.org/wiki/Halting_problem

Google Turing Machine et si vous n'êtes pas au courant.