ハルシネーションと計算可能性理論

本記事は筆者によるプレプリント¹の日本語解説である．本記事で解説する諸結果は，査読済み引用論文からの結果を除き，査読を経ていないことに注意．

大規模言語モデル（Large Language Model）を用いたAIシステムにおいて厄介なのがハルシネーション（hallucination）である．ハルシネーションは偽な言明，非妥当な推論，存在しない情報源などを（しばしば自信満々に）もっともらしく答える現象である．

AnthropicやOpenAIなどのモデルプロバイダが提供するフロンティアモデルは膨大なコーディング作業をそつなくこなし，難しい数学の入試問題を解いたりしてくれる．

一方，プログラミングにおいてもトレーニングデータの乏しい領域²では，前述の高いパフォーマンスが嘘であったかのように，存在しないAPIを使っていかにも正しそうだが動かないコードを出力してしまったりする．ユーザ側で事前に十分に美しいアーキテクチャを組まないと，とにかく動けば良いとでもいうような美しくないコードを出力したりする．数学においても，論理の長い連鎖を必要とする領域や高度な直観を要する領域³では，絶妙なごまかしを紛れ込ませることでいかにも正しそうだが間違った証明を出力する⁴．

こうした領域では，LLMの出力の確認と訂正をユーザ自身が行っていると，最初からLLMを使わず自分でやった場合と比較して手間は増えて品質は下がるだけ，という最悪な結末に至ることも多い．これはコストやクオリティの問題に過ぎないが，福祉・医療・インフラ領域ではハルシネーションが文字通り致命的な結果を齎すこともありうる．

本稿で扱うのは，ある種のハルシネーションが絶対的に不可避であり，かつハルシネーションの緩和と問題解決能力との間にはトレードオフが存在する，という数学的事実である．

ハルシネーションの不可避性

実はハルシネーションが不可避であることは簡単に示せる．

物事をバグらせることに並々ならぬ拘りのある読者ならば，嘘つきのパラドックスでもCurryのパラドックスでも，ありとあらゆる言語的パラドックスを引き起こせるだろうということに気付くかもしれない．LLMには（トークナイズされるが）自然言語でクエリを投げることができ，その文法に何らの制限もないからである．

しかし，たとえそうしたパラドクシカルな現象を引き起こせないように（数学の形式化と同様）入力可能な文法を制限しても，ハルシネーションはなおも不可避であることが示せる．

決定的な回答の強制下でのハルシネーション

前提. LLMには無際限のVRAM/DRAMを含む計算資源が与えられており，いくらでも多くのトークンを処理できるとしておく⁵．

ここでは能力の限界を上から評価しようとしているので，能力を現実よりも高く仮定する分には問題ないだろう．

次のようなシステムプロンプトを考えよう：

ユーザはあなたに真偽を判定したい命題をプロンプトとして与える
あなたはその命題の真偽を判定してTrueかFalseで答えよ

そして，何でもいいので定義可能⁶だがTuring計算不能な集合 $A$ を用意しておき，

$$n \in A?$$

を問うプロンプトを次々とLLMに投げていく．

例えば，実行可能なPythonスクリプトについて，計算が停止するか否かを問う問題（停止性問題 $\mathrm{Halt}$）は計算不能であることが知られているから，停止するPythonスクリプト全体の成す集合を $A$ とすればよい．

すると次のいずれかが必ず生じる：

1. システムプロンプトに違反する．つまりTrueかFalseで答えるという指示に違反する
2. ある入力 $n$ に対して間違った回答をする．つまり，$n\in A$ であるのにFalseと答えるか，$n \notin A$ であるのにTrueと答える

なぜなら，もしそうでないとすれば，当該LLMを使って $A$ を計算できてしまい，$A$ が計算不能であるとの仮定に反するからである．

人工知能研究がいくら発展しようと，モデルがいくら巨大になろうと，GPUがいくら高性能になろうと，決してハルシネーションからは逃れられない．何なら上記証明はLLMに限る必要がない．エキスパートシステムでも自動定理証明でも何でも構わない．ありとあらゆる計算システムに適用可能である．

計算可能理論に基づく定式化

これは数理論理学者を学んだ者にとっては退屈な結果かもしれない．何故なら，停止性問題を含む種々の計算不能（決定不能）問題の存在は，1930年代には既に知られていた⁷ものであって，上記のハルシネーションの不可避性は，これらお馴染みの結果の自明な言い換えに過ぎないからである．

定義. $\Sigma$ をアルファベット，$\Sigma^{\ast}$ をその上の有限文字列全体の成す集合とする．

定理. $A\subseteq \Sigma^{\ast}$ を計算不可能集合とする．次を満たす計算可能関数 $f\colon \Sigma^{\ast} \to \set{\mathtt{True}, \mathtt{False}}$ は存在しない：

1. $x\in A \implies f\left(x\right)=\mathtt{True}$
2. $x\notin A \implies f\left(x\right)=\mathtt{False}$

証明. 集合の計算可能性の定義そのもの．◻︎

なお，Turing機械モデルよりも真に高い計算能力を持つ計算（hypercomputation）が物理的に実現可能であったとしても，この不可能性結果からは逃れられない．ハイパーコンピュータに関する停止性問題はハイパーコンピュータでは計算不能であることが，Turing機械の停止性問題の場合と全く同じ方法で証明できるからである．単に計算不可能性の問題がハイパーコンピュータにおける計算不可能性の問題にシフトするだけである．

ここでは原理的計算可能性を考えたが，実際的計算可能性すなわち計算複雑性における対応物を考えることもできる．現実のAIシステムの計算量は極めて制限されているのだから，計算可能集合であっても高い計算複雑性を持つ場合には，それに対応するクエリの族についてハルシネーションの不可避性が言えることは直ぐに分かる．

計算可能性及び計算複雑性とハルシネーションとの関係についての詳細な議論はXu, Jain and Kankanhalli (2024)⁸, Wang et al. (2026)⁹などを参照．

ハルシネーションと回答能力のトレードオフ

回答保留（Abstention）

ハルシネーションは，事実と異なる情報や存在しない情報を，もっともらしく生成してしまう振る舞いである．これを低減するための研究は様々あるが¹⁰，そのひとつが回答の保留（abstention）である．つまり分からない事柄，確信度が低い（自信のない）事柄については，回答を控えるよう振る舞わせるものである．

Abstentionについては面白い研究が色々とある．特に面白いのは「ユーザーはAbstentionを好まない」という誠に不都合な真実を指摘するものである．ユーザーは確からしくない事柄について回答を控える慎重なAIよりも，嘘でも堂々と回答してくれるAIの方を選好するという研究もある¹¹¹²．つまりユーザからのフィードバックをそのまま学習に使ってしまうと，かえってハルシネーションを助長してしまうというわけである．

とはいえ，回答を適切に保留することができれば，ハルシネーションを回避できるという考え方自体は正しい．極端なことを言えば，全てのクエリに対して「回答保留」と言っておけば，ハルシネーションは起きないとも言える．つまり，ここで問題となるのは，ハルシネーションを防げるかどうかではなく，ハルシネーション（対策）と回答能力（カバレッジ）との間にあるトレードオフである．

トレードオフの定式化

定義. $A, B \subseteq \Sigma^{\ast}$ を互いに交わらない集合とする．集合 $S$ が $A$ を $B$ から分離するとは，$A \subseteq S \subseteq B^{c}$ が成り立つことをいう．このような $S$ として計算可能なものが取れないとき，$\left(A,B\right)$ は計算的分離不能（computably inseparable）であるという．

定理. $\left(A,B\right)$ を計算的分離不能対とする．次を満たす計算可能関数 $f\colon \Sigma^{\ast} \to \set{\mathtt{True}, \mathtt{False}, \mathtt{Abstein}}$ は存在しない：

1. $x\in A \implies f\left(x\right)=\mathtt{True}$
2. $x\in B \implies f\left(x\right)=\mathtt{False}$

証明. さもなくば $f^{-1}\left(\set{\mathtt{True}, \mathtt{Abstein}}\right)$ は $A$ を $B$ から分離する計算可能集合となって矛盾する．◻︎

$A$ を $B$ から分離する任意の集合 $S$ について，$S$ への帰属関係を問う問題を考える．回答保留も誤答も許容するが，少なくとも $A \cup B$ では正答することを要求する．もし $A$ と $B$ が計算的分離不能ならば，この要件を満たすシステムは存在し得ないというわけである．

ちなみに計算的分離不能対は存在する．しかも極めて自然な例がいくつも存在する．

事実. 計算的分離不能対は存在する．とくに，$T$ をGödel–Rosserの不完全定理の前提条件を満たす任意の理論とするとき，$T$ において証明可能な閉論理式全体の集合と，$T$ において反証可能な閉論理式全体の集合は，計算的枚挙可能な計算的分離不能対となる．

互いに交わらない計算的枚挙可能集合は，一方の補集合を使えば分離できることが直ぐ分かる．ただしその計算可能性クラスは $\Pi_{1}$（よって極限計算可能）であっても計算可能とは限らない．そこで，どれくらい計算可能に近い集合での分離が可能かという問題が考えられる．これについては超低（superlow）集合で分離できることが知られている．証明は $\Pi^{0}_{1}$–強制法による¹³¹⁴．

まとめ

決定的な回答を強制するときハルシネーションが不可避であることは定義可能な計算不可能集合の存在から自明である．自然言語そのものにはオブジェクト言語とメタ言語の区別がないためにパラドクシカルであるという問題もあるが，たとえ無矛盾であるような形式的体系に問題を絞ったとしても不可避性は解消されない．

回答保留を許容すればハルシネーションは緩和できる．しかしその場合は正答できるクエリのカバレッジと，誤答や回答保留の回避との間にトレードオフが生じる．そしてこのトレードオフが決定的に不可避であることは計算的分離不能対の存在から自明である．

とはいえこの手の原理的不可避性は現実のAI開発者や利用者にとってはあまり役に立たないかもしれない．知識の片隅に書き留めておいて，原理的に不可能な問題に挑戦して時間を溶かすのを避ける程度で良い．ちょうど各種の決定不能問題の存在がそうであるように．

余談: 人工知能分野と理論計算機科学との断絶について

最近の機械学習分野ではこの手の不可避性定理が何度も再発見されているようにみえる．数理論理学の周辺を学んだことのある読者なら，原理的な不可避性については直ぐに思い至るだろうと書いた．民間伝承的定理（Folklore）と言ってもいいかもしれない．それが再発見されているということは，機械学習と数理論理学/理論計算機科学との間で分野的断絶が生じていることを示唆する．ハルシネーションの原理的不可避性の論文⁸の第二著者Sanjay Jainは計算論的学習理論の教科書¹⁵の共著者でもあるので，この辺りの結果は熟知しているだろう．

もちろん既存の定理を現代的な文脈の中に位置付け直すことそのものには意義がある．筆者のプレプリントの目的も専らそれにある．それでも「ほとんど自明」ならわざわざ論文にはしない．論文になっているということは，少なくとも応用先からは非自明と見做されたということであろう．

初期の人工知能研究は数理論理学と不可分の関係にあった．かつて人工知能研究でよく使われていたプログラミング言語LISP（1960–）の言語仕様は殆どラムダ計算そのものである．ラムダ計算は論理学者Alonzo Churchが数学の形式化のために導入し¹⁶，後に計算体系として再構築されたものである．論理プログラミングの代表的な言語であるProlog（1972–）は述語論理におけるコンパクト性定理の精緻化であるHerbrandの定理に基づく．おそらく，この時代の人工知能研究者が現代のLLMを見れば，ハルシネーションの原理的不可避性はほぼ自明と考えたのではないか．もっとも確かめられるものではないが．

ソフトウェアサイエンスにおいても同様である．計算可能性理論の簡単な議論により原理的に不可能であることが証明できる問題について，それを（ヒューリスティクスではなく厳密に）解くシステムを開発しようとしている場面はしばしば観察される．

かつて人工知能研究の中心であった論理的妥当な記号的推論の連鎖によって回答するAI（いわゆる記号的AI）システムは，現代では機械学習ベースのAIシステムの圧倒的なパフォーマンスの影に隠れてしまっている．90年代にはソフトコンピューティングといって，ニューラルネット，ファジィ論理，カオス理論などが数理科学を超えて産業界まで巻き込んで流行し，ファジィ制御を使ったファジィ家電が販売されるほどになった時期もある¹⁷¹⁸．現在はニューロだけがリバイバルしている状況である．

コンピュータサイエンス専攻でも，TCS専攻でもない限り計算理論などの基礎分野を学ぶことは少なくなってきているかもしれない．しかしながら，コンピュータの可能性とその限界を知るためにも，これらの分野を学ぶ価値は減じていないと信ずる．

1. Takuma Imamura, Hallucination, abstention, and computable inseparability, arXiv preprint, 2026. ↩

2. 筆者の専門分野だとTrusted Execution Environmentsが該当する．この領域では，普通こうなってるだろうという期待が尽く裏切られる魔境であるので，LLMが一次情報に基づかず常識的に推論した場合は高い確率で間違う． ↩

3. 筆者の専門分野であれば，前者は超準解析や項書換え系，後者は位相幾何学などが挙げられる．例えば，組合せ論理におけるBコンビネータの公理 $\left(\left(Bx\right)y\right)z \to x\left(yz\right)$ を与えると，これを結合法則と勘違いして推論してしまったりする．最近のフロンティアモデル（GPT-5，Claude Opus 4.6，Gemini 3以降）ではこの類の間違いは減ってきているが，それでもなお頻繁に起こる．証明が難しいであろう予想のステートメントを，別のステートメントに誤読（あるいは勝手に変更）した後，後者の証明を試みる，ということもよくある． ↩

4. これは証明を自然言語で書かせるのではなく，Isabelle/HOLなりLeanなりの言語で書かせ，ループの中に証明チェックを含めてしまうことで防ぐことができる． ↩

5. そうしないと，単にウィンドウより大きいトークンのクエリを渡されて処理できない結果として間違うという，自明なケースが生じる． ↩

6. 適当な形式言語の論理式の形で記述できるもの．例えば，一階算術の言語においては，非負偶数全体や素数全体は，以下のように論理式で書けるから定義可能である：
   $\set{ x \in \mathbb{N} \mid \mathbb{N} \models \exists y \left(x = y+y\right) }$
   $\set{ x \in \mathbb{N} \mid \mathbb{N} \models x \geq 2 \land \forall y \forall z \left( x = y\cdot z \to x=y \lor x=z \right) }$
   自然数からなる集合全体は不可算無限個存在するのに対し，一階算術の論理式は可算個しかないから，殆ど全ての自然数の集合は定義不可能ということになる．Tarskiの真理定義不可能性定理は算術的定義不能集合の具体例として「$\mathbb{N}$ で真な閉論理式のGödel数全体の成す集合」を与えるものである． ↩

7. Alonzo Church. An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, Vol. 58, No. 2, 1936, pp. 345–363. ↩

8. Z. Xu, S. Jain, and M. Kankanhalli, “Hallucination is inevitable: An innate
   limitation of large language models,” 2024, arXiv preprint. arXiv: 2401.11817 ↩ ↩²

9. Wang, X., Shi, Q., Ding, Z., Gao, J., & Yang, X. (2026). Hallucination as a Computational Boundary: A Hierarchy of Inevitability and the Oracle Escape. Proceedings of the AAAI Conference on Artificial Intelligence, 40(40), 33675–33682. https://doi.org/10.1609/aaai.v40i40.40657 ↩

10. 橘 秀幸, 稲原 宗能, 髙﨑 環, 福地 成彦. LLMとハルシネーション: 基礎と対策, オーム社, 2025. ↩

11. D. B.-O. Nirman, A. Weizman, and A. Azaria, “Fool me, fool me: User attitudes toward LLM falsehoods,” 2024, arXiv preprint. arXiv: 2412.11625 ↩

12. Adam Tauman Kalai and Santosh S. Vempala. 2024. Calibrated Language Models Must Hallucinate. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024). Association for Computing Machinery, New York, NY, USA, 160–171. DOI: 10.1145/3618260.3649777 ↩

13. Carl G. Jockusch and Robert I. Soare, $\Pi^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. DOI: 10.1090/S0002-9947-1972-0316227-0 ↩

14. 正確には，Jockusch and Soareは「任意の計算可能な無限二分木は低次数の無限枝を持つ」ことを証明した．ここで集合 $A$ が低（low）であるとは，$A$ をオラクルとして用いた停止性問題 $\mathsf{Halt}^{A}$ （Turingジャンプと呼ぶ）が通常の停止性問題 $\mathsf{Halt}$ にTuring還元できるときをいう．このTuring還元というのを真理表還元（truth table reducibility，tt–reducibility）に強めたものが超低（superlow）である．Marcus ShaeferはJockusch–Soareの構成が実際には超低次数の無限枝の存在をも示していることを指摘したらしいのだが，Shaefer自身による論文は出版されていない．Jockusch–Soare強制法によって構された低集合のTuringジャンプから停止性問題へのTuring還元において，オラクル使用量（use）がcomputably boundになっていることから，実際にはtt–還元にもなっていることが分かる．詳細は Rodney G. Downey, Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, Springer New York, NY, 2010, DOI: 10.1007/978-0-387-68441-3 を参照． ↩

15. Sanjay Jain, Daniel N. Osherson, James S. Royer, Arun Sharma. Systems That Learn: An Introduction to Learning Theory, MIT Press, 1999. DOI: 10.7551/mitpress/6610.001.0001 ↩

16. 古森雄一. 汎用システムとしての「ラムダ計算+論理」(算術体系の証明論), 数理解析研究所講究録, Vol. 1533, 39–48, 2007. http://hdl.handle.net/2433/58967 ↩

17. 合原一幸 編. ニューロ・ファジィ・カオス―新世代アナログコンピューティング入門, オーム社, 1993. ↩

18. 何なら「ファジィ」は1990年新語・流行語大賞の新語部門・金賞に選ばれている．https://www.jiyu.co.jp/singo/index.php?eid=00007 ↩