見出し画像

計算論入門「停止問題」

かわい しん@論計舎

この記事では計算論の基礎として、アラン・チューリングが否定的に解決した「停止問題」について解説しています。記事の流れは、概要説明から始まり、自然数表記や部分関数の簡単な説明、プログラムの概念の導入を行った後、計算可能性の定義について解説するというものです。
プログラムの概念の導入は補助的なものであり、「プログラム」と呼んでいるものの正体はC言語風のレジスタ機械です。ですので、疑似コードを読める方は、この部分を読み飛ばしてかまいません。

数理論理学・計算理論とは

計算論は数理論理学と理論計算機科学が交わる分野である。その中心的な問いを、関数が計算可能であることが意味するところや計算不可能関数がその不可能性にもとづいてどのように階層わけされるのか、とする。

歴史的にはチューリングによる人間が行う計算という営為の数学的本性の研究 (チューリング機械) やクリーネによる数学の中での計算という操作の数学的本性の研究 (ラムダ計算) が契機の一つとなっている。

こうした数学的道具立てが整い、どのような関数が計算可能なのかを問えるようになった。さらにはどのような、関数をはじめとした諸概念が定義可能か問えるようになった。

諸概念の計算可能性や定義可能性、その不可能性にもとづいた分類が中心的な問いなのである。

まずラフに主要な概念の定義と主結果を与える。

ラフな計算可能性の定義

定義 (計算可能性)

関数が計算可能であるとは、それを計算するプログラムが存在することである。

ここでプログラムと呼んでいるものは、どんなプログラミング言語でもいい。実際、どんなプログラミング言語でも理論的なものも含めてその計算能力が等しいことが経験的に知られている (Cf. Church-Turing Thesis) 。

以下、具体的なプログラムを便宜的に準備して、それに従って議論を進める。　

その前に原義的なプログラミング言語によるプログラムの例を確認しよう。

例 (最小公倍数を計算するプログラム)

least_common_multiple(x, y) {
Int a;
  a = 1;
  while (a < x * y){
    if ((a % x == 0) &&(a % y == 0))
      return (a);
    else
      a++;
    }
    return(x * y);
}


さてそれでは、主結果を紹介する。停止問題とは、「計算が停止するか否か」を予め判定するアルゴリズムの存在を問うものであり、今回紹介するチューリングの定理は、それを否定的に解決したものである。

定理 (Turing 1936) のラフなステートメント

プログラムが停止するか否かをその実行前にアルゴリズム的に判定することはできない。

それでは本論に進もう。ただしその前にいくつかの約束と今回大事になる関数の捉え方、部分関数という考え方を紹介する。

自然数とその約束、部分関数

  • 本記事では、$${0}$$以上の整数のことを 自然数 という。

  • 自然数全体の集合を$${\mathbb{N}}$$と表す。

  • 自然数の有限列$${(n_1,n_2,\dots,n_k)}$$のことを$${\vec{n}}$$などと表す。

  • 自然数の$${k}$$個の自然数からなる有限列$${(n_1,n_2,\dots,n_k)}$$全体の集合を$${\mathbb{N}^k}$$と表す (以降、このような場合に「$${k}$$なんとか」と呼ぶことにします) 。

関数の捉え方

「対応表が先にあってそれが関数を規定しており、対応表こそが関数の実体である」と考える。

対応表

定義 (部分関数)

$${\mathbb{N}^k}$$から$${\mathbb{N}}$$への対応表のことを$${k}$$変数部分関数という。その対応表のもととなっている部分集合をこの部分関数の定義域という。

  • $${f(\vec{n})\downarrow}$$: 部分関数$${f}$$が$${\vec{n}}$$で値をもつ、すなわち下段が空欄でない。

  • $${f(\vec{n})\uparrow}$$: 部分関数$${f}$$が$${\vec{n}}$$で値をもたない、すなわち下段が空欄である。

例 (部分関数)

doubleの対応表

この対応表に相当する関数には、以下のような複数の「実装」が考えられるが、どちらも同じ関数であると考える:

  • $${x+x}$$

  • $${2x}$$

dの対応表

この対応表に相当する関数は、自然数上の$${2}$$変数部分関数$${d(x,y) = (x+1) \div y}$$である。
ただし$${\div}$$は小数点以下を切り捨てて結果を自然数にする割り算である。これは$${\mathbb{N}^2}$$から$${\mathbb{N}}$$への部分関数であり、定義域は$${\{(x,y) \in \mathbb{N}^2 \colon y \neq 0\} }$$である。

プログラムという考え方

このパートは、計算可能性を定義するために便宜的にプログラムを定義する。先に述べたように、どんなプログラミング言語でも計算可能な関数の全体は一致するので、とりあえずひとつ選んでしまおうというわけである。
すでにプログラムを書く向きにあっては、このパートを読み飛ばしたほうがわかりやすいと思われる。

代入文

変数 = 数式;

代入文を実行すると、右辺の数式の値が計算された後に、その値が左辺に代入される。

インクリメント文

変数 ++;

これを実行すると、この変数の値が$${1}$$増やされる。

デクリメント文

変数 --;

これを実行すると、この変数の値が$${1}$$減らされる。

if文

If (条件式) {
    文の並び
  } else {
    文の並び
}

条件式とは、「真」か「偽」の値をとる式で、このif文を実行すると、条件式の値が計算されて、それが真である時は前半に並んだ文が一通り実行され、偽の場合は後半に並んだ文が一通り実行される。

while文

while (条件式){
  文の並び
}

これを実行すると「条件式の値が計算されて、それが真ならば文の並びが一通り実行される」ということが、条件式の値が真である限り繰り返される。

プログラムの構成要素

数式

「変数」や「整数定数」から「整数演算子」や「すでにプログラムに書かれた関数名」を組み合わせて得られる式、整数の値をとる。

整数演算子

 +, -, *, /, %

比較演算子

 ==, !=, <, <=, >, >=

論理演算子

&&, ||, !

例 (数式)

(least_common_multiple(8,6)+1) * (-4)

least_common_multiple()は例で紹介したプログラムに書かれた関数名。

定義-例 (条件式)

!((x % 3 == 0) && (x % 5 == 0))
((x % 3 != 0) || (x % 5 != 0))

これらは同じ値を持つ:
「xの値が15の倍数でない場合は真、15の倍数の場合は偽」。

二つの数式を比較演算子で結んだものとそれらを論理演算子で結んだものを条件式という。

定義 (プログラム)

プログラムは以下の形をしている。

FUNCTION_NAME (INPUTS) {
  DECLARATION
    BODY
}

例 (最小公倍数を計算するプログラム)

least_common_multiple(x, y) {
Int a;
  a = 1;
  while (a < x * y){
    if ((a % x == 0) &&(a % y == 0))
      return (a);
    else
      a++;
    }
    return(x * y);
}

計算可能性

便宜的に定義したプログラムを用いて計算と計算可能性を定義しよう。

定義 (計算)

$${k}$$は自然数、$${P}$$は$${k}$$入力プログラム、$${f}$$は自然数上の$${k}$$変数部分関数とする。$${P}$$が$${f}$$を計算する、とは、任意の自然数$${n_1,n_2,\dots,n_k}$$に対して、次が成立することである。
$${f(n_1,n_2,\dots,n_k)\downarrow}$$ならば$${P}$$の入力変数に$${n_1,n_2,\dots,n_k}$$をセットして実行開始すると$${f(n_1,n_2,\dots,n_k)}$$の値を戻り値として実行を終了する。
$${f(n_1,n_2,\dots,n_k)\uparrow}$$ならば$${P}$$の入力変数に$${n_1,n_2,\dots,n_k}$$をセットして実行開始すると永久に止まらない。

定義 (計算可能性)

自然数上の$${k}$$変数部分関数$${f}$$が計算可能であることは、$${f}$$を計算する$${k}$$入力プログラムが存在することである。

諸定理

ついに主結果の紹介である。

万能関数

次のような仕様を持つ関数$${\text{comp}}$$を定義できる：

  • 「プログラムのコード」と「そのプログラムに対する入力値のコード」から「その実行で返される値」を返し、

  • 「その実行」が止まらない場合は、$${\text{comp}}$$の計算も止まらない。

なお、$${\langle \ast \rangle}$$で表されることもある「xxのコード」は「xxを表す数」と思ってくれてかまわない (最後に少しコメントをしています) 。

定理

任意の計算可能部分関数$${f}$$に対して自然数$${p}$$が存在して、次が成り立つ。
$${f (\vec{x}) = \text{comp} (p, \langle \vec{x} \rangle)}$$

このようにプログラムを表す$${p}$$の値を変えることで、$${\text{comp}(p,\langle \ast \rangle)}$$はどんな計算可能部分関数の代わりにもなる。これにより$${\text{comp}}$$は万能関数と呼ばれる。

定理

重要なのは万能関数が計算可能であることである:

万能関数は計算可能である。

証明の方針

$${\text{comp}}$$を計算するプログラムを書けば十分である。

部分関数$${\text{comp}}$$の定義域は$${\mathbb{N}}$$これを定義域外の場合は、$${0}$$を返すように変更して得られる全体で定義された関数を$${\text{comp}^+}$$と名付ける。
すなわち、$${\text{comp}^+(p,x)}$$の値は、「$${p}$$が表すプログラムを$${x}$$が表す入力可能で実行可能かつ値が返ってくるならばその値、それ以外の場合は$${0}$$」である。

定理 (拡張された万能関数の計算不可能性)

$${\text{comp}^+}$$は計算不可能である、

証明

  • $${\text{comp}^+}$$が計算可能であるとして矛盾を導く。

  • $${1}$$変数全域関数$${\text{diag}}$$を次で定義する: $${\text{diag}(x)= \text{comp}^+(x, \langle x \rangle)+1 }$$

  • つまり$${\text{diag}}$$の値は$${x}$$で表される1入力プログラムに入力$${x}$$を与えた実行が止まるならば、その戻り値に$${1}$$を足したものであり、

  • 止まらないまたは実行不可能であるならば、$${1}$$である。

  • $${\text{comp}^+}$$が計算可能であるという仮定と$${\text{diag}}$$の定義から$${\text{diag}}$$は計算可能である。

  • したがって$${\text{diag}}$$を計算するプログラムが存在し、そのコードを$${N}$$とできる。

  • すると、$${\text{comp}^+}$$の定義と$${N}$$が全域関数$${\text{diag}}$$を計算するプログラムのコードであるから、

  • $${\text{comp}^+(N, \langle x \rangle)=\text{diag}(x)}$$

  • これより$${\text{diag}(N)=\text{diag}(N)+1}$$

  • 関数　$${\text{diag}}$$の全域性よりこれは矛盾。

  • 証明終わり。
    なお、「全域関数」とは部分関数のうち、対応表の下段がすべて埋まっているものである。

停止問題

$${2}$$変数関数$${\text{halt}}$$を次のように定義する。
$${\text{comp}(p,x)\downarrow}$$のとき、$${1}$$、$${\text{comp}(p,x)\uparrow}$$のとき、$${0}$$。
これはプログラムと入力値のコードが与えられるとその実行が止まるか否かを答える関数である。

停止問題の否定的解決

$${\text{halt}}$$は計算不可能である。

仮に$${\text{halt}}$$を計算するプログラムがあるとする。
すると、これを用いて$${\text{comp}^+}$$を計算するプログラムが下記のように書けてしまう。
これは先の定理に反する。

comp_plus (p, x){
  if (halt(p, x) == 1)
    return(comp(p, x))
  else
    return(0);
}

証明終わり。

まとめ

以上の停止問題の否定的解決は、次のようにまとめられます。

  • 計算の問題を対象レベルの万能関数のみに帰着させる。

  • 「計算が停止するか否か」というメタ判断を対象レベルで正確にシミュレートする$${\text{comp}^+}$$を考える。

  • $${\text{comp}^+}$$の計算不可能性により、「計算が停止するか否か」をあらかじめ判定するアルゴリズムが存在しないことがわかる。

このメタとオブジェクト (対象) の行き来と、万能関数という考え方が重要な点なのです (実際、チューリングは1936年の論文の多くを万能関数の構成に費やしています) 。

また、$${\text{comp}}$$の定義で$${\langle x \rangle}$$という記法、「コード」という言葉とそれを表す'$${\langle \ast \rangle}$$'が出てきました。「コード化」を簡単にいうと記号列を数字に落とし込む手法のことです。これにより計算機にすぎなかったチューリング機械で一般的な情報処理ができるようになります。
現代では、プログラムをプログラムに投げられることは当たり前でしょうが、それを可能にしているのが、「コード化」です。

コード化を解説している動画があるのでぜひご覧ください。

またこの記事は論計舎YouTube動画「計算論入門「停止問題」」に対応します。よろしければこちらもご覧ください。


参考文献

  • Turing, Alan Mathison. "On computable numbers, with an application to the Entscheidungsproblem." J. of Math 58.345-363 (1936): 5.

  • 鹿島亮. "C 言語による計算の理論." サイエンス社 (2008).

  • 照井一成. "コンピュータは数学者になれるのか?: 数学基礎論から証明とプログラムの理論へ." 青土社 (2015).

  • Cooper, S. Barry. “Computability theory. “ Chapman and Hall/CRC, 2017.

謝辞

原稿に目を通してコメントと示唆を下さった論計舎講師のみなさん特に尾崎さんと、友人popysonさんと川村花道さんに感謝を申し上げます。

最後に

最後までお読みいただきありがとうございます。

論計舎では生徒さんを募集中です。詳しくは論計舎webサイト [link] をご覧ください。今回の記事のいっそうな詳細も学べます。また、無料の教材も公開しております。論計舎webショップ [link] よりDLいただけます。

いいなと思ったら応援しよう！

かわい しん@論計舎
数理論理学と計算機科学のオンライン私塾論計舎の代表。論と計の科学についての情報を発信していく予定です。