計算能力と複雑さの不可能性:常に最終的に対角引数によるものか?

Computabilityでは、問題が再帰的ではなく、再帰的に列挙できないことを証明したい場合は、例えば、他の非再帰的または非r.e.これらの技法は、いくつかの対角引数の存在のおかげで、またはそれに直接基づいています(つまり、あるプログラム$
M $は入力プログラム$ M ‘$とは逆の動作をします) 、$ M = M ‘$は矛盾している)。 Complexityでは、($ P
neq NP
$などの未確認の主張に関係なく)何らかの問題をできないことがあることを証明したい場合、我々は最終的には(例えば、時間階層の定理は$
EXPTIME $ – 完全な問題が$ P $にないことを証明するが、その定理も対角引数を使って証明される)。

だから私の質問は次のとおりです。対立的な議論のために、すべての重要な不可能性が計算能力と複雑さ(実際の不可能性、未解決の結果まで不可能ではない)最終的にすなわち、コンピューティビリティと複雑さの中の私たちの重要な「不可能な知識」は、プログラムがプログラムを実行するのに十分強力であるという事実から来ていますか?

最終的に斜めの議論によるものではない唯一の重要な不可能な結果は、Ackermann関数が原始的な再帰的なものではないということです。この明らかな「ルール」の他の重要な反例を見逃していますか?

EDIT(11月18日):私の質問は特に対角線の議論そのものに焦点を当てていたことを暗示して申し訳ありませんが、プログラムの自己参照(対角引数、ベリーパラドックスなど)に依存するすべての議論にもっと興味があります。より単純な言語(例えば、正規または文脈自由)に対しては、これらの言語がどのように構築されるかに基づいて(例えば、ポンピング補題)、「構造的に」不可能な議論がある。しかし、再帰的またはr.e.不可能な結果のほとんどは、プログラムの自己参照に強く依存しています。これは私が意味していたものです。

ベストアンサー

ソートの標準比較モデルの下限、およびデータ構造のほとんどのセルプローブモデルの下限は無条件です(モデル内での計算では同じですが、Turingマシンの下限についても同じことが言えます)。対角化ではなく情報理論に依存します。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です