アーサー・デントは、地球上でまだ利用できない宇宙時代の技術を使用して、TM M1 が空のテープで開始されたときに停止するかどうかを判断するアルゴリズムを開発しました。しかしその後、彼は人生、宇宙、そしてすべての意味が42であることを発見しました.
(a) [5] 与えられた TM M2 に対して、Arthur が既に開発したプログラムを使用して、入力 42 で M2 が停止するかどうかを判断できることを証明してください。プルーフで新しい TM を作成する場合は、そのマシン スキーマを指定します。
(b) [5] Arthur のプログラムよりも高速であるが、TM M2 が入力 42 で停止するかどうかという質問に答えるプログラムがあるとします。Arthur がこのアルゴリズムを使用して、空白で開始したときに一部の TM M1 が停止するかどうかを判断する方法を説明してください。テープ。プルーフで新しい TM を作成する場合は、そのマシン スキーマを指定します。
(c) [5] 私たちはクラスで、TM M が空のテープで開始されたときに停止するかどうかを判断する問題は決定できないことを証明しました。TM M が入力 42 で停止するかどうかを判断することも決定不能であることを証明するために使用できるのは、部分 (a) または部分 (b) ですか?
私の教授がここで話していることを解読するのを手伝ってくれる人はいますか?