1入力でマシンをチューリングするための問題を停止します

Question

私の質問は：

チューリングマシンとオラクルの停止が、特定のチューリングマシンがすべての入力で停止したかどうかを決定できないことを示す「嘘つき」プログラムと同様の簡単な構成があります。

嘘つきプログラムについて話すとき、次のような場合の矛盾があるため、チューリングマシンが他のすべてのチューリングマシンの停止を判断できないという標準証明を参照しています。

def Liar(T):
   if Halts('T(T)'):
      loop()
   else:
      return

.

停止したオラクルを持つことができることを見ることができます。

通常のチューリングマシンレベル0を呼び出すと、チューリングマシンとオラクルレベルの停止を呼び出すことができます.1。リアルプログラムを使用している証明は、レベル1マシンが独自の問題を維持することを示すために同じように機能することを見ました。それらのためにはできません。

Answer 1

「嘘つき」プログラムを呼び出すことは、通常、Cantorの対角度化引数に似ているため、通常、 Diagonalization引数と呼ばれます。

通常、私たちが一定の財産ですべての要素を列挙しようとすると、私たちは必ずしも「不正確な」要素を指摘していることを指摘することができます。それ自体に関して財産を満足させない（これは完全に手動波状ですが、あなたが議論を見たことがあるならば、あなたは私が何を意味するのか理解しているのを理解するでしょう）。

今、尋ねているのは、ALL_TM（TM普遍性）がOracleを持つTMによって決定されないことを示すために同じことができるかどうかです。

ええと、そうではありません。少なくとも自然な方法ではありません：ALL_TMを決定し、その後他のMachine N（あなたが "嘘つき"マシンを呼び出すこと）を決定するOracleマシンMが存在すると仮定することから始めなければならないでしょう。 NでNを実行したときの矛盾 ただし、マシンNは標準的なTMではなくOracleマシンである必要があります（またはM内のOracleの電力を失うことになる）。しかし、NのOracleは入力標準のTMSとなるため、Nの内部動作はどういうわけかOracleにフィードするための標準のTMを作成する必要があります。これは自然な建設のようです、そしてそれは確かに単純ではないでしょう。

今、おそらく、この主張のための直接の対角化引数を与えるいくつかの畳み込み方法があるが、直接の請求を証明すること（すなわち、all_tmがOracle To Oracleを停止させたTMが決定できないと）はそうではないと考えることはできません。削減などの標準的なツールを使用して困難です。