どうも、木村（@kimu3_slime）です。
集合論の歴史を調べるうちに、その流れでゲーデルの不完全性定理のような数理論理学が生まれただけではなく、そこからコンピュータの基礎となる計算機科学が生まれてきたことに興味を持ちました。
論理を扱っていたはずなのに、いつの間にか計算の理論になっている……素人目には、そんな不思議な印象があります。
今回は、コンピュータ科学の教科書「計算理論の基礎」を読んで考えたこと、計算とは何か、いかにしてモデルされたか、その限界は？について、自分なりにまとめてみます。
「計算」とは何か
計算とは、日常的な意味では、物を数えること、足し算や掛け算などの演算を行うこと、結果を予測して行動することなどを意味します。
電卓は、とてもシンプルな計算機ですね。数値を入力し、演算を施した結果を返してくれます。電卓以前では、そろばんといった計算機もありました。しかし、現代のコンピュータ（計算機）は、電卓・単なる数値計算に還元されないようなことをしている気がします……一体、それは何なのでしょうか。
それが、アルゴリズムです。簡単に言えば、手続き・過程（process）を伴った計算です。
この概念を生み出すきっかけとなったのは、数学者ヒルベルトが出した23の問題のひとつ（第10問題）です。
\[ \begin{aligned}6 x^3 y z^2 + 3xy^2 – x^3 -10=0\end{aligned} \]
この方程式は、\[ \begin{aligned}x=5,y=3,z=0\end{aligned} \]という解を持っています。より一般に、整数係数の（n次の）多項式による方程式を、ディオファントス方程式と言います。
ヒルベルトは、ディオファントス方程式が整数解を持つかどうかを、有限回の演算で決定できるプロセスを求めよ、という問題を出しました。
この「有限回の演算で決定できるプロセス」こそが後にアルゴリズムと呼ばれることになるものですね。一般のディオファントス方程式の解そのものを求めるのは難しい。まずは、解を持っているかどうかだけでも判定したい。
しかし、それは不可能であることが、1970年にYuri Matijaševićにより証明されました。ディオファントス方程式が整数解を求めるためのアルゴリズムは存在しないのです。
ヒルベルトの問題は否定的に解決されましたが、彼の問題提起が、「不可能であることを証明するにはどうしたらいいか？」「アルゴリズムとは何か？」を厳密に考えるきっかけとなっています。
参考：Hilbert’s Tenth Problem is Unsolvable
いかにしてモデル化されたか：チューリングマシン
では、アルゴリズムとは何でしょうか。計算の手続き……というのが素朴な定義ですが、これでは厳密に扱えません。
その定義は、チャーチ・チューリングの提唱（Church-Turing Thesis）によって与えられました。すなわち、アルゴリズムとは、チューリングマシン（Turing Machine）によって与えられるものである、と。
チューリング・マシンは、チューリングによって1936年に論文「計算可能数とその決定問題への応用（On computable numbers, with an application to the entscheidungsproblem）」で提唱された仮想の機械です。
（チャーチもチューリングも、計算機科学の巨匠として知られています。）
チューリングマシンとは何か。これを詳しく解説すると非常に長くなってしまうので、概念的に重要だと思うポイントをシンプルにまとめてみます。
チューリングマシンは、オートマトン（単：automaton、複：automata）と呼ばれる計算機のモデルの一種です。論理と数学の言葉を使い、概念上で計算機と呼ばれるものを作るとしたら……という話。
オートマトンは状態機械（state machine）とも呼ばれ、内部状態と状態が変化する規則（遷移規則）がその基本です。
最もシンプルなオートマトンは、有限オートマトン（finite state automata）と呼ばれるものです。（特に決定性オートマトン）
画像引用：Automata theory, Cepheus – Wikipedia
上の図を見てください。\(S_1,S_2\)というのが2つの状態（state）です。伸びている矢印は、状態変化のルール、すなわち遷移（transition）の規則を示しています。1や0は入力に対応する記号であり、電気のオンオフと考えるとわかりやすいでしょう。
入力は0101といった文字列で表されます。入力に対して、オートマトンは受理（accept）または拒否（reject）という出力を返します。入力を処理し終わると受理状態になるときは受理、そうでないときは拒否といったように。
図では\(S_1\)が開始状態かつ受理状態で、0101は受理されます（矢印をたどってみてください）。例えば、2つの状態をドアのオンオフに対応させれば、自動ドアのプログラムを表現することができます。この図では状態はたったの2種類（1ビット）ですが、より複雑な計算もこのようなモデルを考えれば作れます。
厳密に言えば、有限オートマトンとは、5つの組\(Q,\Sigma,\delta,q_0,F\)のことです。\(Q,\Sigma\)は、それぞれ状態、アルファベットと呼ばれる有限集合。\(\delta: Q\times \Sigma \to Q\)は遷移関数で、図でいう矢印に対応するもの。\(q_0\in Q\)は初期状態、\(F\subset Q\)は受理状態の集合。これらは、集合論の言葉によって書かれています。
参考：集合の定義、よく使う数の集合、ラッセルのパラドックスとは
チューリングマシンは、有限オートマトンをより高度にしたものです。状態（メモリ）が（可算）無限であり、状態を書き換えることができ、受理状態や拒否状態に入るとすぐに停止するといった特徴が加わります。
アルゴリズムとは何か。特定の（例えば0と1のみを使った）文字列による入力を読み取り、定められた規則にしたがって状態を変化させ、その入力を受理するか拒否するか判断する。計算の手続き……というふわっとした定義より、だいぶ具体的になりました。
僕が数学しか知らない立場から勉強して驚きだったのが、計算の問題を、言語処理の問題に帰着させているということです。
ここでいう言語とは、僕たちが普段使っている自然言語ではなく、形式言語のことです。a,b,cや1,2,3といった文字（記号、symbol）を並べたものを文字列（string）と言い、文字列の集合を言語（language）と言います。
入力は記号のみを受け付けるからといって、その応用は狭いものではありません。むしろ、万能なものになります。例えば、2*3=6といった計算や数学的計算は、論理式（formula）という特殊な文字列（数）として捉えられます。（論理式を数に対応させることを記号化、ゲーデル数化という）
論理式を入力し、それに対して正しいか正しくないかというアウトプットを返せる機械があれば、それは数学的命題の真偽をアルゴリズム的に確かめることそのものです。
（原理的には計算できる…と言っても、チューリングマシンによる言葉：マシン語をそのまま人間が読み書きするのは大変。そのために、アセンブラや、コンパイラを使ったプログラミング言語が生み出されていきました。僕たちが現代でプログラミング言語を扱うときに意識はしませんが、原理的にはチューリングマシンを使って計算していると言えるでしょう。）
計算機モデルの限界とは
本を読み進めると、計算機のモデルのアイデアは面白いが、限られたものしか計算できないのではないか……ということに思い至りました。
結局、有限オートマトンも、チューリングマシンも、文字列というインプット形式、つまり可算無限集合がベースとなっています。もともとは有限の手続きを探すアイデアなのだから、それは当然と言えば当然です。
参考：無限集合の多さ（濃度）はどのくらい？ 可算無限、カントールの対角線論法とは
だから、実数のような数をそのまま扱うことや、非可算無限の集合を相手にした問題は計算できないのではないか。こうした問題を考えるために生まれてきたのが、計算可能性（computability）の理論と呼ばれるものです。
実際、チューリングは停止性問題（halting problem）を解くチューリングマシンが存在しないことを示しました。
停止性問題とは、あらゆる入力に対してきちんと停止するチューリングマシンが存在するかどうかを、判定できるかどうかという問題です。「ループしない」マシンであることを、マシンによって判別しきることはできないのです。
またその数学への応用として、次のような結果が知られています。
定理 6.11
\(\text{Th}(\mathcal{N},+,\times)\)は判定不可能である。
定理 6.13
\(\text{Th}(\mathcal{N},+,\times)\)の中の証明可能な命題の集まりはTuring認識可能である。
定理 6.14
\(\text{Th}(\mathcal{N},+,\times)\)に属する真の命題には証明可能でないものがある。
引用：計算理論の基礎 6章 pp.234-239
\(\text{Th}(\mathcal{N},+,\times)\)は、自然数の足し算と掛け算によって表される論理式のうち真の命題を集めたもので、自然数の理論と呼ばれます。
ある言語がTuring認識可能とは、ざっくり言えば、その言語による入力を受理するチューリングマシンが存在すること。判定可能とは、入力に対して受理もしくは拒否を返すチューリングマシンが存在すること。チューリングマシンは、入力に対し、受理でも拒否でもなく計算が終わらない、ループする可能性があるのです。
判定可能ならば認識可能ですが、その逆は言えません。判定可能性は受理か拒否か、真偽を決定する能力を持っていますが、認識可能性は真のみを捉える能力で、偽を弾くことが求められない。
上に述べた定理からは、足し算と掛け算を使った（比較的シンプルに思える）命題群であっても、証明可能かどうかはわからない命題が存在すること、すなわち一般的な数学の命題の真偽を判定するアルゴリズムは存在しないことがわかります。これは数学にとっても大きな発見です。
その証明は、停止性問題に帰着されます。さらにその証明は、ゲーデルの不完全性定理の証明で行われているような対角線論法が鍵となっています。自己言及しているような問題では、可算な集合を使っては対応しつくせなくなるのです。
参考：「ゲーデルの不完全性定理」を誤解しないために、数学の歴史的流れを解説
まとめ
後半少し細かすぎたでしょうか、ざっくりと振り返ります。
- 計算とは：問題を解くための手順、すなわちアルゴリズム。
- 計算のモデル：記号化された入力に対し、正しいか正しくないか判別できる。入力に応じて状態が変化し、出力が決まる。
- 計算の限界：種々の問題は解けるが、原理的に解けない問題もある。
「計算理論の基礎」は、情報系（計算機科学）を学ぶ人にはおすすめの教科書ということで、学部1年生くらいの頃に買ったのですが、その頃にはなんだか難しくて放置していました。
今読んでみると、集合論の下地があるので、非常に読みやすいです。数学科のカリキュラムでは計算機科学の内容が入っていないことが多いですが、セットで学びやすい分野と言えます。
学生の頃、「自分の専門は数学だから…」と言い訳をして情報数学を学んでいなかったのがもったいなかったです（笑）。特に理論計算機科学は、単なる数学の応用ではなく、むしろ応用として数学的な結果（ヒルベルト第10問題の否定的解決のような）が得られます。
コンピュータが日常生活や産業に応用されているのは言うまでもありませんが、20-21世紀の科学研究において、シミュレーションやコンピュータを使ったアプローチは多く生まれています。やや強引ですが、数学が諸科学に応用され役立つことを説明する例として、コンピュータはわかりやすいです。
その基礎となる集合論や計算機科学が、もっと多くの人に、より簡単に学ばれるようになってほしいな、と思います。
僕自身も、諸科学における数学の応用を学び、わかりやすく面白い話を書いていきたいです。
木村すらいむ（@kimu3_slime）でした。ではでは。
こちらもおすすめ
集合論前夜、いかにして論理は記号化されたか？ ライプニッツ、ド・モルガン、ブール
「ゲーデルの不完全性定理」を誤解しないために、数学の歴史的流れを解説
