NhacVibe
Ảnh bìa なぜプログラムが止まるかを、事前に判定できないのか?

なぜプログラムが止まるかを、事前に判定できないのか?

つるチャンネル · 3,8 N lượt xem · 14 thg 10, 2026

Mô tả

TypeScriptで1000まで数える型を書くと、「無限に続くかもしれない」というエラーが出ます。
999までなら通るのに、なぜ1000では止められるのでしょうか。

実は「プログラムが止まるかどうか」を、あらゆるプログラムについて必ず正しく判定する方法は存在しません。
1936年にアラン・チューリングが示した「停止性問題」です。

では、実際のプログラミング言語や解析ツールはどうしているのでしょうか。

この動画では、TypeScriptのTS2589から始めて、数学の未解決問題、Leanによる停止性の証明、Windowsドライバの解析に使われたTERMINATOR、そして2024年に決着した5状態2記号のBusy Beaverまで、「プログラムが止まるとはどういうことか」を順番に見ていきます。

鍵になるのは、「止まる」「止まらない」に3つ目の答えを加えることです。

▼目次
0:00 1000まで数えたら「無限かもしれない」
0:57 止まるかは、待つしかない?
2:15 5行のループと280年の未解決問題
4:38 3つ目の答え「わからない」
7:21 止まる理由を探す(TERMINATOR)
9:33 人類はどこまで当てられるか(BB(5)・2024年)
12:26 まとめ

▼この動画で確かめたこと
・TypeScript 7.0.2
999までは通り、1000と-1では同じTS2589
(末尾再帰の条件型は1000回で打ち切り)

・Lean 4(live.lean-lang.org・v4.35.0-rc4)
コラッツの関数では "fail to show termination" となり、
termination_by? は termination_by 10 - n を提案

・動画内の5行のループはBigIntで実装
numberでは2^54付近でnが増えなくなるため、ゴールドバッハ予想との対応が崩れます

▼参考資料
・A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936)
・B. Cook, A. Podelski, A. Rybalchenko, "Termination Proofs for Systems Code", PLDI 2006
・B. Cook, A. Podelski, A. Rybalchenko, "Proving Program Termination", Communications of the ACM, 2011
・Byron Cook, "A gentle introduction to automated reasoning", Amazon Science (2021)
・The bbchallenge Collaboration, "Determination of the fifth Busy Beaver value" (arXiv:2509.12337)
・bbchallenge.org
・T. Oliveira e Silva ほか, ゴールドバッハ予想の 4×10^18 までの検証
・H. G. Rice, "Classes of recursively enumerable sets and their decision problems" (1953)
・TypeScript: microsoft/TypeScript
・Kysely公式