理論計算機科学におけるゾンビ的誤解

理論計算機科学におけるゾンビ的誤解

序論

• Michael Sipser の教科書 "Introduction to the Theory of Computation" には完璧な課題がある
• 課題: "f:{0,1}*→{0,1} 関数が神の存在に応じて 1 または 0 を返すとき、f は計算可能か?"
• 答え: "はい、f は計算可能である"（定数関数は計算可能であるため）

計算可能性の概念

• 計算可能性は関数や無限列に適用される
• 個別のはい/いいえの質問や個別の整数には適用されない
• プログラムを書く難しさは計算可能性と無関係である

P 対 NP 問題

• P 対 NP 問題は個別のはい/いいえの質問である
• NP 困難性は関数や言語に適用される
• P 対 NP 問題は計算不可能でも NP 困難でもありえない

Busy Beaver 関数

• Busy Beaver 関数は計算不可能である
• BB(6) のような個別の整数は計算可能である
• BB 関数全体は計算不可能である

理論計算機科学におけるゾンビ的誤解

• 無限列や関数に適用される概念を、個別の整数や未解決問題に誤って適用すること
• 停止問題の計算不可能性とゲーデルの不完全性を混同すること

読者への質問

• このゾンビ的誤解をどう防げるかを読者に問う

GN⁺の要約

• この記事は、理論計算機科学で頻繁に起こる誤解を扱う
• 計算可能性は関数や無限列に適用され、個別の整数やはい/いいえの質問には適用されない
• P 対 NP 問題は個別の問いであり、NP 困難性の概念とは無関係である
• Busy Beaver 関数は計算不可能だが、個別の値は計算可能である
• この記事は、理論計算機科学の基本概念を明確に理解するのに役立つ

[GN⁺]

Hacker Newsの意見

• Kolmogorov複雑性を計算するアルゴリズムの存在可否は無限性と関係している

  • 任意の長さを持つ文字列のKolmogorov複雑性を計算するアルゴリズムは存在しない
  • しかし、長さがn未満の文字列のKolmogorov複雑性を計算するアルゴリズムは存在する
  • これは、あり得るすべての文字列に対する巨大なルックアップテーブルを作る方式で可能である
  • 有限の問題は常にプログラムで解けるが、無限の問題はそうではない

• 構成的数学のほうが人々の直感によりよく合うという意見

  • P=NP問題に対するプログラムが存在するという証拠はまだない
  • Mark Bravermanはすべての（二次）Julia集合が計算可能であることを証明したが、これは一様には計算可能ではない
  • 構成的数学では複素平面を複数の領域に分け、各領域内のJulia集合がコンパクトであることを証明する

• 停止問題の決定不能性を理解しにくい理由

  • return true と return false のプログラムのどちらか一方は常に正しい答えを返す
  • 決定可能性は、無限の機械/入力の組み合わせへ拡張されたときにのみ決定不能になる

• モーダル論理が必要な問題の表現

  • 「fは計算可能か？」という問いは、モーダル的には誤った問いである
  • 「fは計算可能だろうか？」という問いのほうがより正確である
  • これはコンパイラディレクティブやpragmaに似ている

• 関数fの紛らわしい表現

  • 関数fは「God exists」の値に応じて分岐しない
  • fが0であれ1であれ計算可能である
  • 混乱は自由変数を分岐条件に押し込むことから生じる

• 決定可能性、計算可能性、存在などの意味の違い

  • 学術的文脈と日常的文脈では意味が異なる
  • 大きな数は学術的には存在し計算可能だが、実際には宇宙に収まらない

• 「God exists」に関する問いの問題点

  • 「God exists」が真か偽かは明確ではない
  • これは自然言語と数学を混ぜたときに生じる問題である

• 理論計算機科学と複雑性理論がCS学部生にとって難しい理由

  • NP-hardのような用語は、大衆的な比喩や想像に置き換えられる

• ブログのテキスト強調方式に対する不満

  • 選択したテキストの背景色が変わらず、直感的ではない

• 「God exists」を別の数学的命題に置き換える提案

  • 「God exists」を真または偽として明確に定義すべきである