サマリー

計算可能性理論における最も有名な問題「停止問題」。本記事では、論計舎の川井新氏による講義を元に、初心者でも理解できるように計算論の基本、部分関数の定義、そして停止問題の不可能性証明までを図解・コード例付きで解説します。

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』
照井一成『コンピュータは数学者になれるのか？』