Turing-Maschinen und Maschinenschemen

Question

Arthur Dent, mit Raumalter Technologie noch nicht verfügbar auf der Erde entwickelte einen Algorithmus, wenn ein TM M1 stoppt bestimmt oder nicht, wenn sie auf ein leeres Band gestartet. Aber dann später entdeckte er, dass der Sinn des Lebens, das Universum und alles ist 42.

(a) [5] Bei einem TM M2, beweisen, dass Arthur wenn M2 stoppt oder nicht auf dem Eingangs bestimmen kann 42 das Programm mit er bereits entwickelt, wenn ein TM M1 stoppt bestimmt oder nicht, wenn sie auf ein leeres Band gestartet. Wenn Sie ein neues TM in Ihrem Beweis erstellen, gibt seine Maschine Schema.

(b) [5] Angenommen, es ist ein Programm, das schneller als Arthur, aber es beantwortet die Frage, ob ein TM M2 Aussetzer auf Eingang 42. Erklären Sie, wie Arthur diesen Algorithmus verwenden können, wenn einige TM M1 stoppt zu bestimmen, wann gestartet auf ein leeres Band. Wenn Sie ein neues TM in Ihrem Beweis erstellen, gibt seine Maschine Schema.

(c) [5] Wir in der Klasse bewiesen, dass das Problem, wenn ein TM M stoppt der Bestimmung, wenn sie auf ein leeres Band begann nicht entscheidbar ist. Ist es Teil (a) oder Teil (b), die verwendet werden kann, um zu beweisen, dass es auch unentscheidbar ist, wenn ein TM M Aussetzer auf Eingang 42, um zu bestimmen?

Kann mir jemand helfen entziffern, was meine prof über hier spricht?

Answer 1

Willkommen in einige wirklich kompliziert Informatik Theorie. Versuchen Sie starten hier: http://en.wikipedia.org/wiki/Halting_problem

Google Turing-Maschine als auch, wenn Sie sich damit nicht vertraut sind.