チューリングマシンとマシンスキーマ

Question

Arthur Dent、宇宙年齢のテクノロジーを使用して地球上でまだ利用できないことは、TM M1が空白のテープで開始されたときに停止するかどうかを決定するアルゴリズムを開発しました。しかし、その後、彼は人生、宇宙、そしてすべてが42であることを発見しました。

（a）[5] TM M2を与えられた場合、Arthurは、M2がすでに開発したプログラムを使用して入力42を停止するかどうかを判断できることを証明します。証明に新しいTMを作成する場合は、マシンスキーマを提供します。

（b）[5]アーサーのプログラムよりも速いプログラムがあると仮定しますが、入力42でTM M2が停止するかどうかの問題に答えます。アーサーがこのアルゴリズムを使用して、ブランクで開始したときにTM M1が停止するかどうかを判断する方法を説明してくださいテープ。証明に新しいTMを作成する場合は、マシンスキーマを提供します。

（c）[5]クラスで、TM Mが空白のテープで開始されたときに停止するかどうかを判断する問題は決定できないことを証明しました。それは、TM Mが入力42で停止するかどうかを判断することも困難であることを証明するために使用できるパーツ（a）またはパート（b）ですか？

誰かが私の教授がここで話していることを解読するのを手伝ってくれますか？

Answer 1

本当に複雑なコンピューターサイエンス理論へようこそ。ここから始めてみてください： http://en.wikipedia.org/wiki/halting_problem

Google Turing Machineも慣れていない場合は。