証明と計算複雑さのパラドックスの公式化?

ZFCプルーフの長さと人間の書かれた長さについては、正式なプルーフに関するいくつかの記事を読んでいます(私の前回のcstheoryに関する質問も参照してください)証拠)、私はこの明らかなパラドックスを考え出した。

$ M_ {const} $をチューリングマシンに与えたプログラムとする。$ M $は長さ$ | ガンマ|の短いZFC証明$
ガンマ$があるかどうかを調べる。 leq | M | ^ 2 $その$ M $は一定の時間内に実行されます。

Program M_const( M )
  enumerate all strings S of length  <= |M|^2
    verify if S is a proof of "M in O(1)"
      if it is a valid proof the halt and accept
  if no valid proof is found halt and reject 

ここで、(再帰定理によって)それ自身のコードを知っている$ M_ {paradox} $と入力$ x $ まず$ M_
{const}(M_ {paradox})$をシミュレートします。それが受け入れるならば、$ 1 $から$ | x | $へループする
 ($ O(n)$に落ちる)、そうでなければ停止する($ O(1)$になる)。

Program M_paradox( x )
  String M = self_code() //ok by the recursion theorem
  simulate M_const( M )  //simulate M_const on M_paradox
    if it accepts then for i = 1 to |x| do nothing//-> O(n)
    otherwise halts                               //-> O(1)
  some dummy unused code here //see below

それは明らかです(そして、おそらくZFCで証明可能です):

  1. $M_{const}$ always halts and is correct;
  2. if $M_{const}( M_{paradox} ) = Yes$ then $M_{const} notin
    O(1)$ by construction; so we have a contradiction;
  3. so $M_{const}(M_{paradox}) = No $; and we can have:
    • (a) $M_{paradox} notin O(1)$ OR
    • (b) $M_{paradox} in O(1)$ AND there is not a short proof of
      it;

しかし、ケース$(a)$は建設によって保持することはできません。そう …

  1. $ M_ {paradox} in O(1)$
  2. それについての短い証拠はありません;

しかし、ステップ1〜4はZFCで形式化することができます(もし何かが欠落していなければ、その長さは$ M_ {paraox}
$に線形的にしか依存しないので、ダミーコードを$ M_ {paradox} $に加えることができます。そのようなZFC証明は$ |
M_ {paradox} | ^ 2
$(未使用状態を加えるとチューリングマシンのランタイムが変わらないという事実を利用することができます。だから、私たちは、O(1)$の中に$
M_ {paradox} という短い証明がないという5番の点と矛盾する。

Q1。 $ M_ {const}(M_ {paradox})$の出力はどうですか?

Update: There were another question
Q2 here, but it I decided to post it as a new
“Part II” question to avoid confusion.

ベストアンサー

$ def mc {M_ mathit {const}} def mp {M_ mathit
{paradox}} $コメントの中だけに生きていないように、

問題のステップ1-5で与えられた推論は現実の世界で正しい。したがって、$ mc( mp)$はNOを出力し、$
mp(x)$は一定時間で停止しますが、ZFCにはこれの十分な証明はありません。

この議論をZFCで正式化しようとするとき、問題のあるステップは2つです:ここでは、ZFC自体に含意

(1)ZFCが長さ$ le | mp | ^ 2 $の証明によって ‘$ mp $ halts in
constant time’を証明すると、$ mp $は一定の時間で停止します。

一般的に、フォームのステートメント

(2)ZFCが$ phi $、$ phi $を証明するならば。

ZFCのための反射原理の例として知られています。また、Löbの定理(Gödelの第2不完全定理の一般化)によって、ZFC自体は証明できません。
φ$。 ZFCの整合性ステートメントは$ phi = bot
$の反射原則の特殊なケースであることに注意してください。一般的に、反射の原則は一貫性よりも厳密に強い。

我々の場合、$ phi $は$ Sigma ^ 0_2 $の式 “$ mp
$は一定時間で停止する”ので、ステップ2は明らかにZFCの$ Sigma ^ 0_2 $の反映原則に不服を申しますZFCで

However, we have to our disposal an extra restriction that we
ignored so far, namely that we have a bound $le|mp|^2$ on the
length of the purported ZFC-proof of $phi$. Crucially, at this
point, $mp$ is a fixed explicit Turing machine, hence this bound
is a standard integer constant (and likewise, $phi$ is a fixed
sentence). Thus, (1) is actually an instance of the finitistic
reflection principle

(3)$ phi $に長さ$ le s $のZFC証明があれば、$ phi $。

ZFCで実際に証明できるのは、 です。もし$ phi $が長さ$ le s
$のZFC証明を実際に持っていれば、それを受け取り、(3)前提;そうでなければ、各文字列$ | w | le s $に対して、
“検査によって” $ w $が$ phi
$のZFC証明ではないというZFC証明を生成し、これらをまとめて連結することができます、(3)の証明(具体的には、その前提の否定の証拠)を得る。

このブルートフォースプルーフの長さは、$ s ^ 2で指数関数的になります。つまり、$ 2 ^ {O(| mp | ^
2)} $です。実際、$ s $と$ | phi | $には長さの多項式の証明があります:これはPudlak
[1]によって効率的な部分真理述語を使って証明されました。
[2]の改善点は一貫性ステートメントでのみ述べられていますが、より一般的な反映原則にも適用されると考えています。したがって、長さ$
O(| mp | ^ 2)$の(1)のZFCプルーフがあります。

しかし、これはまだ矛盾を起こすには不十分です。(3)$ s
$以上の長さが必要です(ただし、[1,2]の下限はそれほど強くありません)。したがって、(1)のZFC証明は、$ | mp | ^
2 $以上の長さを必要とします。これは、同じ方法で長さパラメータ$ s $を上げるだけで、$ mc $またはpadding $
mp $の範囲を上げることで修正することはできません。したがって、パラドックスはありません。

したがって、要約すると:ZFC は、$ mc( mp)$がNOを出力し、$
mp(x)$が一定時間で停止することを証明するが、証明は少し長すぎる。

また、これらの議論の中の何もZFCに依存しないことに言及する価値があります。同じ推論は、他の多くの理論、例えばPeano算術のために働くでしょう。
(基本的に、有限に多くの公理や素敵なスキーマによって公理化された逐次理論が必要です。詳しくはPudlákの論文を参照してください)。

[1] PavelPudlák、 財務的整合性ステートメントの長さについてLogic Colloquium
’84(Paris、Wilkers、Wilmers、eds。)、論理学と数学の基礎vol。
120、1986、pp.165-196、doi:
10.1016/S0049-237X(08 )70462-2

[2] PavelPudlák、 有限状態整合性ステートメントの長さの範囲の改善 、in:Logic and
Combinatorics(Simpson、ed。)、Contemporary Mathematics vol。
65、American Mathematical Society、1987、pp。309-331、doi: 10.1090/conm/065

返信を残す

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