On the Complexity of the Bi-infinite Post Correspondence Problem

本論文は、チューリングマシンの非停止性からの還元連鎖を提示し、また関連するいくつかの無限およびシフトされた変種の$\Pi^0_1$完全性を証明することにより、双無限ポスト対応問題（$\mathbb{Z}$PCP）が算術的階層において$\Sigma^0_2$完全であることを確立する。

要約

あなたは、2つの無限テープレコーダー、レコーダーGとレコーダーHを使ってゲームをしていると想像してください。あなたにはカードの束があります。各カードには「G面」と「H面」の2つの面があり、それぞれの面には文字の列（例えば「apple」や「banana」など）が書かれています。

ゲームは単純です：カードのシーケンスを選び、それらを積み上げていきます。

• G面を上から下へと読んでいくと、一つの長い文字列が得られます。
• H面を上から下へと読んでいくと、別の長い文字列が得られます。

目標は、Gの文字列とHの文字列が完全に一致するようなカードのシーケンスを見つけることです。これは、典型的な**ポストの対応問題（PCP）**です。これはコンピュータサイエンスにおける有名なパズルであり、あらゆるケースに対して「解が存在する」か「不可能である」と教えてくれる一般的なアルゴリズムは存在しないことが分かっています。

新しいひねり：「双無限」ゲーム

この論文では、このカードゲームよりも複雑な、**双無限ポスト対応問題（ZPCP）**と呼ばれるバージョンを紹介しています。

上から下へと積み上げる代わりに、スタックが両方向に無限に続くことを想像してください：左へも右へも無限に続いています。

• あなたは$-\infty$から$+\infty$まで続く無限のカードのシーケンスを探しています。
• ルールは同じです：無限のGの文字列は、無限のHの文字列と一致しなければなりません。

しかし、一つ注意点があります。文字列が両方向に無限であるため、2つの文字列は必ずしも全く同じ「ゼロ」地点から始まる必要はありません。つまり、**シフト（ずれ）**が生じる可能性があります。想像してみてください、Hの文字列はGの文字列と同じものですが、誰かがそれを少しだけ左または右にスライドさせた状態です。もし、一方をもう一方と完璧に一致するようにスライドさせることができれば、パズルを解いたことになります。

大きな問い：これはどれほど難しいのか？

コンピュータ科学者は、問題を算術階層と呼ばれる梯子（はしご）を使って分類しています。

• レベル1（底の段）： 「決定不能」ではありますが、単一の例を見つけることで証明できる問題です（オリジナルのPCPのようなもの）。
• レベル2（次の段）： これらはさらに難しい問題です。解の存在を証明するためには、特定のやり方で無限の可能性をチェックする必要があるかもしれません。

論文の発見：
著者であるオリビエ・フィンケルとヴェサ・ハラヴァは、この双無限ゲーム（ZPCP）が、この梯子のレベル2に厳密に位置していることを証明しました。

• これは標準的なPCP（レベル1）よりも難しいです。
• しかし、問題の最上部にあるわけではなく、特定の、管理可能な複雑さを持っています。
• 決定的なのは、彼らがこれがレベル1の「易しい」部分には含まれないことを証明したことです。解が存在するかどうかを判断するには、より複雑な論理が必要となります。

どのように証明したのか？（「タイムマシン」の比喩）

これを証明するために、著者たちはこのカードゲームと、チューリングマシン（あらゆるアルゴリズムをシミュレートできる理論上のコンピュータ）の挙動との間に架け橋を築きました。

1. タイムマシン： チューリングマシンを、テープを読み取るロボットだと想像してください。もしロボットが停止せずに走り続けるなら、それは「非停止（non-terminating）」です。もし停止するなら、それは「停止（halts）」します。
2. 翻訳： 著者たちは、翻訳機として機能する特別なルール（半テュー・システム）を作成しました。彼らは次のように示しました。
   • もしロボットが永遠に走り続けるなら、双無限ゲームを解く無限のカードスタックを構築できます。
   • もしロボットが停止するなら、そのようなカードスタックを構築することはできません。
3. 「可逆性」のトリック： 彼らの証明の鍵は、この翻訳機を「可逆的」にすることでした。映画を巻き戻すことを想像してください。もし映画を最初に戻して完璧に巻き戻せるなら、そのシステムは可逆的です。
   • 彼らは、もし解が見つかった場合、そのステップをチューリングマシンの実行の最初へと「巻き戻す」ことができると証明しました。
   • もしマシンが停止（ハルト）していたら、「巻き戻し」は壁（前の動きが存在しない状態）に突き当たります。
   • この「巻き戻し」能力によって、問題はレベル2の特定の複雑さへと押し上げられました。

その他の知見

その過程で、彼らはいくつかのサイドパズルも解決しています。

• 単射モーフィズム： たとえゲームを制限し、すべてのカードがユニークであり、かつどの2つのカードも同じ文字パターンを生み出さない（ゲームが「単射」である）としても、問題は依然として解決不可能であり、同様に難しいままであることを彼らは証明しました。
• 固定シフト： 彼らは、2つの文字列間のシフトが特定の数に固定されているバージョン（例：「Hの文字列は常にGの文字列のちょうど5文字右にある」）についても検討しました。これらもまた、非常に困難（レベル1完全）であることを彼らは証明しました。

結論

この論文は、無限語パズルの「難易度の景観」を描いた地図です。

• 標準的なPCPは「レベル1」の怪物です。
• 双無限PCP（ZPCP）は「レベル2」の怪物です。オリジナルのものよりも厳密に難しくなっていますが、無限に難しいわけではありません。
• 著者たちは、この新しいパズルが数学的宇宙のどこに位置しているかを正確に特定するために、巧みな「巻き戻し」メカニズムを用いました。

要するに、この双方向の無限のカードゲームを解くことは、オリジナルの解決不能なバージョンよりも一段階上の、特定の種類の「難しさ」を持っているということであり、著者たちはそれが数学の世界のどこに位置しているのかを正確に突き止めたのです。

技術概要

技術要約：双無限ポスト対応問題の複雑性について

問題の定義
本論文は、双無限ポスト対応問題（ZPCP）の計算複雑性を調査している。古典的なポスト対応問題（PCP）が、与えられた2つのモルフィズム $g, h$ に対して $g(w) = h(w)$ となる空でない有限語 $w$ を求めるものであるのに対し、無限PCP（$\omega$PCP）は無限語を求め、ZPCPは $g(\alpha) = h(\alpha)$ となる双無限語 $\alpha = \dots a_{-1}a_0a_1 \dots$ が存在するかどうかを問うものである。決定的な違いとして、双無限語における等価性はシフトに関して定義される。すなわち、$g(\alpha) = h(\alpha)$ であるとは、ある整数シフト $\tau$ が存在して、$g(\alpha)$ の位置 $i$ における文字が $h(\alpha)$ の位置 $i+\tau$ における文字と一致することを意味する。

先行研究により、ZPCPは決定不能であり、算術的階層の $\Sigma^0_2$ クラスに属することが確立されているが、その位置は厳密には特定されていなかった（すなわち、$\Pi^0_1$-完全なのか、あるいは階層の第2レベルに厳密に位置するのかは不明であった）。本研究の主な目的は、ZPCPの算術的階層における正確な位置を決定することである。

手法
著者らは、決定性チューリングマシン（TM）の空入力に対する停止不能問題から始まり、半テュー・システムを経て、最終的にPCPの変種へと至る一連の還元経路を構築している。この手法は、以下の主要な技術的構成に基づいている。

1. 可逆半テュー・システム: 著者らは、与えられたチューリングマシン $M$ から特定の半テュー・システム $S_M$ を構築している。このシステムは、$\Theta$-決定論的かつ$\Theta$-可逆であるように設計されている。この可逆性は、最終的なZPCPへの還元において極めて重要であり、これにより、計算ステップを順方向および逆方向の両方向にシミュレートすることが可能になる。
2. 単射的モルフィズムと有界遅延: 本論文では、半テュー・システムをシミュレートするモルフィズム $g$ と $h$ を構築している。重要な技術的貢献は、これらのモルフィズムが「有界遅延 2」であることを証明した点であり、これはそれらが単射であることを意味する。これにより、著者らは決定不能性の結果を単射的モルフィズムのクラスへと拡張することが可能となった。
3. シフト変種: 著者らは、「$s$-シフト」変種（$\omega$PCP$_s$ および ZPCP$_s$）を定義し、解析している。ここで、等価条件は特定のシフト $s$ に固定されている。これらの変種が $\Pi^0_1$-完全であることを証明している。
4. 非同期化とオーバーライン: 双無限の性質を扱い、自明な解を排除するために、記号のオーバーライン付きおよび非オーバーライン付きのコピーと、特定の「非同期化」マーカー（$d^4$ および $f^4$）を用いた複雑なアルファベット構成を用いている。これにより、解が必ず順方向と逆方向の構成の間を行き来するように強制し、半テュー・システムの導出を両方向にシミュレートさせる。

主要な貢献と結果

• $\omega$PCPの複雑性: 著者らは、無限PCP（$\omega$PCP）が、単射的モルフィズム（具体的には有界遅延 2 のモルフィズム）に制限された場合でも決定不能であることを証明した。さらに、この制限されたバージョンが $\Pi^0_1$-完全であることを確立した。
• シフト問題の複雑性: 本論文は、任意の自然数 $s$ に対して、$s$-シフト無限PCP（$\omega$PCP$_s$）および$s$-シフト双無限PCP（ZPCP$_s$）が $\Pi^0_1$-完全であることを証明している。
• ZPCPの複雑性: 主要な結果は標準的なZPCPに関するものである。著者らは、ZPCPが $\Pi^0_1$-困難であることを証明した。ZPCPが $\Sigma^0_2$ に属し $\Pi^0_1$ ではないという既知の結果と、$\Sigma^0_1$ にも属さないこと（$\Pi^0_1$-困難性による）を示す新しい証明を組み合わせ、次のように結論付けている：
  $$\text{ZPCP} \in \Sigma^0_2 \setminus (\Pi^0_1 \cup \Sigma^0_1)$$
  これにより、この問題は算術的階層の第2レベルに厳密に位置することが示された。
• 半テュー・システム: $\Theta$-決定論的かつ$\Theta$-可逆な半テュー・システムの非停止問題は、$\Pi^0_1$-完全であることが示されている。

意義と主張
本論文は、ポスト対応問題の変種に関する複雑性の景観の理解を精緻化したと主張している。具体的には：

• ZPCPの算術的階層における位置に関する曖昧さを解消し、それが $\Pi^0_1$-完全ではなく、厳密にレベル 2 に存在することを確認した。
• 不定性を簡略化するために用いられることが多い単射性や有界遅延といった強い制約の下でも、無限変種の決定不能性と $\Pi^0_1$-完全性が維持されることを示した。
• 著者らは、ZPCPをレベル 2 に特定したものの、それが $\Sigma^0_2$-完全であるかどうかという問いは未解決のままであると述べている。

本研究は、チューリングマシンの停止不能性から半テュー・システムの非停止性へ、そして最終的に様々なPCP変種へと至る、厳密な還元の連鎖に依拠しており、双無限の制約を扱うために構築されたシステムの可逆性を利用している。