圖靈機器和機器圖解

Question

Arthur Dent利用太空時代技術尚未在地球上提供開發了一種算法，用於確定TM M1在空白磁帶上啓動時是否停止。但後來，他發現生命，宇宙和一切的意義是42.

（a）給定一個TM M2，證明Arthur可以確定M2是否停止在輸入42上使用他開發的程序決定了TM M1在空白磁帶上啓動時是否停止。如果您在證明中創建了一個新的TM，則給它的機器模式。 （b）[5]假設有一個程序比Arthur的程序快，但它回答了TM M2是否停止了輸入42的問題。請解釋Arthur如何使用這個算法來確定某個TM M1是在什麼時候停止在空白磁帶上開始。如果您在證明中創建了一個新的TM，則給它的機器模式。 （c）[5]我們在課堂上證明，確定TM M是否在空白磁帶上啓動時暫停的問題不是可確定的。 （a）或（b）部分是否可以用來證明確定TM M是否停止輸入42也是不可判定的？

任何人都可以幫我解釋我的教授在這裏談論什麼嗎？

Answer 1

歡迎來到一些非常複雜的計算機科學理論。嘗試從這裏開始：http://en.wikipedia.org/wiki/Halting_problem

谷歌圖靈機以及如果你不熟悉。