過去・現在・未来

【 Church-Turing Thesisの変化と量子情報理論 】 このセッションが、今回のセミナーに向けた最後のセッションになります。 このセッションでは、「計算可能性理論」から「計算複雑性理論」への発展を、 Church-Turing Thesisの変化・発展として振り返り、あわせてそれが現時点でどのように変化を続けているのかを見ていきたいと思います。 以下は、その大雑把な流れです。 【 1920年代 -- ヒルベルト・プログラム 】 ヒルベルトは、全ての数学的命題の真または偽を決定する方法が 存在すること、数学の形式化が矛盾を含まないことが証明しようと しました。 【 1930年代 -- ゲーデルの不完全性定理 】 ゲーデルは、真または偽を決定する方法が存在しない命題が 存在すること、また、数学の形式化が矛盾を含まないことの証明 が不可能であることを示しました。それはヒルベルトのプログラムが、 遂行できないことを意味しました。 【 1950年代 -- チャーチ＝チューリングのテーゼ 】 「証明可能＝計算可能」なものには限界があることは、1950年代 には、チャーチ=チューリングのテーゼとして定式化され、一般に 広く認められるようになりました。ただ、それは、我々の認識の「限界」と しては、非常に荒い、かつ、抽象的で原理的な限界を与えるもので しかありませんでした。 【 1970年代 -- 計算複雑性理論の登場 】 クック、レビン、カープらは、計算可能だが実際には手に負えない 計算である領域を精緻に分類しようとし、計算複雑性理論が生ま れます。 「難しい計算」が「易しい計算」には還元できないことを主張する 「P = NP ? 問題」は、現在も未解決です。 【 1980年代 --  チャーチ＝チューリング＝ドイッチェのテーゼ 】 ドイッチェは、ファインマンの自然をシミュレートする量子コンピュータというアイデアに刺激を受けて、計算は、物理的な過程として実現されると主張して、チャーチ=チューリングのテーゼを拡大しました。ただ、80年代は、まだ、量子コンピュータは物理学者の頭の中の概念としてしか存在していませんでした。 【 1990年代 -- 量子複雑性理論とショアのアルゴリズム 】 ベルンシュタインとバジラーニによって、量子複雑性の理論が登場し、BQPという新しい複雑

【 量子チューリングマシンとBQPクラス 】 1993年に、Bernstein と Vazirani は、これまでのTuringマシンの拡大である「量子Turingマシン」を新しく定義して、その上で複雑性理論を展開しました。 ここから始まったこの複雑性理論の新しい分野を「量子複雑性理論」と呼びます。量子複雑性理論は、現在の複雑性理論の中心分野です。 量子複雑性理論で最も基本的なクラスは、BQPです。それは、従来の複雑性理論での多項式時間で決定可能な複雑性のクラス P に相当するものです。 ただし、量子Turingマシンの特性として、その出力は古典的なTuringマシンのように常に確定した値を返すのではなく確率分布として与えられます。 BQPは、“Bounded error, Quantum, Polynomial time” の略です。 この Bounded error は、このマシンの出力の「誤り」が一定の確率（一般には 1/3 を使う）以下であることを表しています。 その点では、BQPは古典的な複雑性理論でのBPP (bounded-error probabilistic polynomial time)によく似ています。 【 量子コンピュータの理論的可能性をめぐって先行した議論 】 「量子コンピュータ」は、今から約40年前(1982年)のFeynmanの洞察を発端とします。彼の論文に刺激を受けて DeutschがChurch=Turing Thesis を拡大することを提案します(1985年)。その後、 Vaziraniが量子チューリングマシンを構成し、量子複雑性の基本的クラスBQPを提案します。(1993年) この間の理論展開は、目覚ましいものです。 こうした流れの頂点は、1994年のShorの、量子コンピュータによる素因数分解のアルゴリズムを発見です。 「量子コンピュータ」が広く注目され研究者が爆発的に増大します。 このセッションでは、これらの議論の概略を紹介したいと思います。スライドを参照ください。 【 Church = Turing テーゼの拡大 】 この間の議論で注目すべきことは、「計算可能性理論」のエッセンスとしての「Church = T uring テーゼ」の拡大の動きです。 古典的なChurch = Turing テーゼは、次のようなものでし

【 確率的チューリングマシンとBPPクラス 】 #コンピュータと数学2 今回のセッションでは、「確率的チューリングマシン」と呼ばれるチューリングマシンの拡大の話をします。 「確率的チューリングマシン」の構成の仕方は、前回見た「非決定性チューリングマシン」の構成とよく似ています。 「確率的チューリングマシン」の振る舞いを説明する前に、「非決定性チューリングマシン」の振る舞いについて、少し補足しておこうと思います。 【 前回のセッションの補足 】 前回のセッションで、「非決定性チューリングマシン」の振る舞いを説明したblog記事で、「チューリングマシンの拡大では、新しい計算を定義することに意味がある」というような少し極端な議論を述べました。また、それに対して、一つの入力に対して実行のたびに異なる結果を返すような「計算」に意味はないという当然の意見も紹介しました。 ここで補足したいのは、「非決定性チューリングマシン」は、見かけほど無茶苦茶な計算を定義しているわけではないと言うことです。 次のことに注目してください。 一つには、「非決定性チューリングマシン」は、複数（それは膨大な数になるかもしれないのですが有限です）の並行に動作する「決定性チューリングマシン」でシミレート可能だということです。前回のセッションで見たように、「非決定性チューリングマシン」を、そのツリー構造の中で「決定性チューリングマシン」を表すパスを指定するテープを追加すれば、「決定性チューリングマシン」でシミュレートすることが可能です。 　 それが非決定論的に振る舞うように見えるのは、それが概念的には、無数の（有限個です）決定論的に振る舞うチューリングマシンの可能な全体を表現しているのに、我々が 見るのは、そのうちの一つのチューリングマシンの出力だけだからです。 【 非決定性チューリングマシンがある入力をaccept あるいは reject する条件 】 注目すべきもう一つのことは、先のことと関係しているのですが、「非決定性チューリングマシン」がある入力を「受理 (accept)」または「拒否 (reject)」する条件です。 大雑把に言えば、チューリングマシンがある入力を「accept」すると言うのは、その入力が表す命題が正しいと認めることで、「reject」すると言うのは、その入力が表す命題を正しく

【 非決定性チューリングマシンとNPクラス 】 このセッションから新しいPart 「チューリングマシンの拡大と複雑性クラス」が始まります。 「計算可能性理論」のエッセンスは、「計算可能な計算はすべて、ある帰納的チューリングマシンによって実行されるものである」という「チャーチ=チューリングのテーゼ」です。 このテーゼによれば、「計算可能な計算」という数学的な性質は、「あるチューリングマシンによって実行されるもの」として、ある機械（チューリングマシン）の振る舞いと対応づけられることで定義されています。 興味深いことは、「計算可能な計算」という数学的な性質と機械の振る舞いを結びつけるこの「テーゼ」自身は、数学的な命題では無いことです。それは、人間の数学的認識の特徴について語っているのですが、数学的に証明されるような性質のものではありません。 「チャーチ=チューリングのテーゼ」自体を拡大することも可能です。実は、「量子コンピュータ」の登場は、そうした「テーゼ」の見直しと深い関係があります。それについては、このあとのセッションで見ていきたいと思います。 【 チューリングマシンの振る舞いを変える 】 このセッションでは、「テーゼ」の枠組みを大きく変えるのではなく、チューリングマシンの概念を拡大してその振る舞いを変えることを考えてみましょう。新しい数学的性質を定義するのが目的です。 　　「ある数学的性質 Lの計算とは、ある拡大された 　　チューリングマシンMで実行されるものである」 こんな感じなのですが、一つ問題があります。それは、「チューリングマシンの拡大」は、口で言うほど簡単ではないからです。 そもそもチューリングマシンは数学的には万能で、「帰納的チューリングマシン」ならは、計算結果が返る計算可能なものは、すでにすべてカバーしています。（「帰納的」という条件を外した、一般のチューリングマシンには、「停止」する保証はありません。） このセッションで行う、チューリングマシンの拡大は次のようなものです。 「普通のチューリングマシンは、一つの入力に対して一つの出力を返す」 「それがどうした」 「我々は、チューリングマシンを、一つの入力に対して複数の出力を返すように拡大する」 「そんなのチューリングマシンと言わない」 「だから、「拡大」だと言っているだろ」 「どうすんの？」 「普通の

【 AIとの対話の「心得」としての Interactive Proof 】 グラフの認識がむづかしいことを示す例として、グラフの非同型問題を取り上げたのですが、AIと私たちの関係を考える上で、Interactive Proofの考え方を知っているのは意味があるように感じています。 「AIはなんでも知っている」と考える人もいれば、「AIは嘘ばかりつく」と考える人もいます。「AIが進化すれば、人間を超えて全知全能に近づく」と信じている人もいます。 現代のAI技術の到達点では、AIがInteractive Proofの全能な証明者の役割を果たすにはまだまだ遠いのはいうまでもないことですが、AIをProverの位置においてInteractive Proofの劣化版（Proverの能力が格段に劣ると言う意味です）のアナロジーを考えると、いろいろ面白いことに気づきます。 Interactive Proofの枠組みで重要なのは、「証明者」の与える「証明」は「検証者」による検証を経なければ「証明」としては受け入れられないということです。劣化版のアナロジーで言えば、AIの言うことは、「検証者」によって検証されなければ、正しいとはみなされないと言うことです。検証者は、もちろん、我々です。 AIでのfew shot プロンプトは、正しい答えに辿り着くための手法ですが、検証者が繰り返しAIに問いを投げかけることを通じて、AIが知らないことをあぶり出すことも可能です。 この劣化版のアナロジーが秀逸なのは、AIが嘘をつくことを織り込み済みだと言うことです。本家のInteractive Proofで、Proverが嘘をつくのは、グラフの非同型問題について言えば、Proverがプロトコル上必ず答えを返すことを義務付けられているからです。このことも、ハルシネーションが生まれるメカニズムの一端を説明するのかもしれません。 時間があったら、現代のAIと対話する上の「心得」として、Interactive Proofの知識が役に立つと言う話をしたいと思います。

   【 2月に開催したマルレク「言語の意味の数学的構造」の講演ビデオと講演資料を公開しました 】#言語の意味の数学的構造  2月に開催したマルレク「言語の意味の数学的構造」の講演ビデオと講演資料を公開しました このセミナーで扱っているのは、Tai-Danae Bradley らが、アメリカ数学会のジャーナルNotice誌の2024年2月号に投稿した次の論文です。  　　“The structure of meaning in language: 　　parallel narratives in linear algebra and category theory”　  https://www.ams.org/journals/notices/202402/rnoti-p174.pdf この間、マルレクでは 数学者Tai-Danae Bradley の大規模言語モデルの数学的構造に対する研究を紹介してきました。 　⚫️大規模言語モデルの数学的構造 I　 https://www.marulabo.net/docs/llm-math/ 　　#大規模言語モデルの数学的構造1 　⚫️大規模言語モデルの数学的構造 II　 https://www.marulabo.net/docs/llm-math2/ 　　#大規模言語モデルの数学的構造2 それは、大規模言語モデルの性能に強い印象を受けたTai-Danaeが、大規模言語モデルの意味把握の新しいカテゴリー論的数学モデルを提案した、とても興味深いものでした。 今回紹介する Tai-Danae Bradley の論文で、彼女はもっと大胆な主張を展開しています。 それは、大規模言語モデルを構築しているAI研究者の言語理論を「ニューラル言語モデル」論として、正面から批判しているものです。 【 「ニューラル言語モデル」批判の要点 】 「意味と形式は切り離せないという考え方は新しいものではないが、現在のAIをめぐる哲学的な議論には浸透していない。」 「構文対象の分析において意味が問題になるとすれば、それはすべて言語の形式に反映された構造的特徴に起因するということである。」 「しかし、現在のニューラル言語モデルが不十分なのは、まさにこの点である。というのも、ニューラル言語モデルは、そのタスクを実行する際に必然的に働く構造的特徴を明らかにしてい

   【 1月の マルレク「大規模言語モデルの数学的構造 II 」の講演ビデオと講演資料、公開しました 】 #大規模言語モデルの数学的構造2 1月27日に開催した、マルレク「大規模言語モデルの数学的構造 II 」の講演ビデオと講演資料、公開しました。ご利用ください。 このセミナーは、12月30日に開催した、マルレク「大規模言語モデルの数学的構造 I 」 https://www.marulabo.net/docs/llm-math/  の後編です。この前編・後編二つのセミナーで主要に紹介するのは、大規模言語モデルの不思議な振る舞いを数学的に説明することを目指した、Tai-Danae Bradleyたちの次の論文です。 　　"An enriched category theory of language: from syntax to semantics" 　　 https://arxiv.org/abs/2106.07890 前編については、今回の「Part 1 第一部のふりかえり」で概要をまとめてあります。 今回公開した後編は、前編で紹介した copresheaf 意味論というカテゴリー論的アプローチを、単位区間 [0,1] をｍenrich化して拡大し、言語表現の「継続」に確率を導入し、大規模言語モデルの数学的モデルとして提案するという、前掲の論文の中心部分です。 このセミナーで利用されているカテゴリー論の基礎については、Tai−Danae Bradley らがMIT Pressから出版した"Topology A Categorical Approach" の"0 Preliminaries"  のパートが、とてもいいまとめになっています。オンライン版は、無料で読めます。一読をお勧めします。 https://topology.mitpress.mit.edu/ 以下、今回公開した後編のパートごとに、内容を紹介します。 【 「Part 1 第一部のふりかえり」の概要 】 言語を構成する意味を持つ文字列である、語・フレーズ・文・文の連続 ... を「表現」とします。任意の表現 𝑆, 𝑇 について、表現Sの文字列が表現Tの部分文字列であるとき、𝑆 ≤ 𝑇と順序を定義します。この順序は、反射律と推移律を満