「停止問題」から学ぶ計算の理論入門 ― プログラムが止まるか止まらないかを事前に判定できるのか？
サマリー
計算可能性理論における最も有名な問題「停止問題」。本記事では、論計舎のYouTube講義を元に、初心者でも理解できるように計算論の基本、部分関数の定義、そして停止問題の不可能性証明までを図解・コード例付きで解説します。
1. 計算の理論とは？
計算論（理論計算機科学）は、「何が計算可能で、何が不可能か」を明らかにする学問分野です。TuringやKleeneが提唱したこの分野では、人間や機械が行う“計算”という行為を厳密に捉えます。
本記事の目的：
停止問題という一例を通して、「計算の限界」について直感的に理解すること。
2. 関数と部分関数の基礎
「関数」とは、入力に対して出力を返すルールですが、すべての入力に出力が定義されていない関数は「部分関数」と呼ばれます。
例：d(x, y) = (x+1) ÷ y （ただし y ≠ 0 の場合）
3. プログラムで関数を計算するとは？
以下のようなプログラムを例に、関数の計算をプログラムで実行する意味を定義します。
least_common_multiple(x, y) {
int a = 1;
while (a < x * y) {
if ((a % x == 0) && (a % y == 0))
return a;
else
a++;
}
return x * y;
}
4. 停止問題とは？
問題設定
あるプログラム P と入力 x が与えられたとき、
「P(x) が停止するか否か？」を判定する関数 halt(p, x) を定義したい。
結論
そのような関数
halt(p, x)は計算不可能である。
5. 停止問題の証明概要
-
halt関数が存在すると仮定 -
comp+という全域関数を定義 - 自己言及的な
diag関数で矛盾を導く
comp_plus(p, x) {
if (halt(p, x) == 1)
return comp(p, x);
else
return 0;
}
6. Turing の洞察と現代的意義
Turing が1936年に提案した「チューリングマシン」は、今も計算理論の基本です。彼は当時まだ存在しなかったコンピュータの本質を、紙と鉛筆で行う人間の計算行為の観察から定式化しました。
参考文献
- 鹿島亮『C言語による計算の理論』
- S. Barry Cooper『Computability Theory』
- 照井一成『コンピュータは数学者になれるのか？』
以下は、あなたの記事の末尾に追加するのに適した動画紹介セクションです。文体・構成はご指定のZenn記事に準拠し、対象動画「計算論入門『停止問題』」に合わせてカスタマイズしています。
🎥 解説動画：停止問題についてさらに深く学びたい方へ
本記事の内容をより体系的に理解したい方のために、YouTubeにて
**「計算論入門『停止問題』」**という解説動画を公開しています。
- 計算とは何か？という問いに対する理論的アプローチ
- 計算可能性の定義、部分関数、万能関数の導入
- 停止問題の証明とその不可能性の直感的な理解
などを丁寧に解説しており、プログラミング経験者や数学初学者でも理解しやすい内容になっています。
📌 動画内目次
00:00 ステッカー
00:20 オープニング
01:59 計算の理論とは
03:30 ネタバレ（結論の先出し）
06:05 表記について
06:42 部分関数の説明
09:18 プログラムの導入と構文
13:36 計算の定義と例
15:36 万能関数 comp の構成
17:46 停止問題の主張と証明スケッチ
19:06 チューリングとコンピュータ誕生
20:58 参考文献の紹介
21:10 エンディング
🔗 参考資料とリンク
- スライドPDF：計算論入門「停止問題」スライド
- 論計舎ウェブサイト：https://ronkeisha.net
- お問い合わせ：https://ronkeisha.net/contact/
- Twitter（論計舎）：@ronkeisha_info
- Twitter（川井 新）：@squawai
必要に応じて、Zenn 記事末尾にこのセクションをコピー＆ペーストしてご活用ください。デザインや表現の微調整が必要であればお申し付けください。
Discussion