こんにちは。今回もコンピュータの歴史について紹介していきます。

前回のバベッジによる「解析機関」から時間が経過し、
第二次世界大戦が開戦する前の1936年に、アラン・チューリングによって
「コンピュータ」とは何かを決定づける論文が発表されました。

そのタイトルは

”On Computable Numbers, with an Application to the Entscheidungsproblem”
(計算可能数について、Entscheidungsproblemへの応用を交えて)

です。

“Entscheidungsproblem”とは、ドイツ語の単語で決定問題と呼ばれるものです。

決定問題とは、「どんな数学的な記述を入力しても、真理値(真か偽かを示す値)を出力できるような機械が存在するかどうか」
というもので、17世紀にライプニッツによって提起されました。

決定問題は、1928年に、デビット・ヒルベルトと、
ヴェルヘルム・アッカーマンによって改めて提起されました。

ヒルベルト自身は、1930年頃には、「解けない問題は存在しない」と考えていたようですが、その結果は 否定的 なものとなりました。
つまり、アラン・チューリングが論文で発表した結論は、
「どんな問題でも解けるすごい機械は存在しない」 というものです。

残念な結論となってしまいましたが、結論以上に重要なのは、
チューリングがこの論文の中で導入した仮想的な チューリング・マシン なのです。

チューリング・マシンについて説明します。
個別の「セル」が無限に並んだものすごい長さのテープが存在するとします。「セル」には、0か1か印をつけることができます。

「ヘッド」はテープに沿って動作する機械 で、「セル」の情報を読み取ることができます。
そして「テーブル」は、「セル」の情報と「状態」を組み合わせて、
次の「ヘッド」の動作と「状態」を決める対応表となります。

ヘッドはテープからセルの情報を読み取り、次の動作や状態を変化させながらさまざまな動作を行います。

チューリングマシンの具体的な説明をwikipediaより引用します。

「チューリング・マシンは、1936年にアラン・チューリングによって発明されたもので、
「a-machine」（自動機械）と呼ばれていました。このモデルを使って、
チューリングは2つの疑問に否定的に答えることができた。

(1) テープ上の任意の機械が「円形」であるかどうかを判断できる機械は存在するのか
(例:フリーズするか、計算タスクを継続するのに失敗するか)
(2) テープ上の任意の機械が与えられた記号を印刷するかどうかを判断できる機械は存在するのか

このように、任意の計算が可能な非常に単純な装置の数学的記述を提供することによって、
彼は計算の性質を一般的に証明することができました、
特に「決定問題」の計算不可能性を証明することができました。」

数学的に厳密にチューリングマシンを定義することで、このチューリングマシンによって解ける問題と解けない問題があること示しました。

また、チューリングは、任意のチューリングマシンをシミュレートできる万能チューリングマシンを考案しました。

万能チューリングマシンについて説明します。

先程説明したような、普通のチューリングマシンを考えます。
「テーブル」 にはさまざまな動作が書かれています。

今回は、数値と四則演算ができる電卓のようなものを考えます。

これ以降、これを「電卓マシン」と呼びます。

そして、電卓マシンとは別に、新たなチューリングマシンを考えます。

まず、 「電卓マシン」の「テーブル」を0と1の文字列にエンコードし、新たなチューリングマシンに読み取らせるテープに表現します。

また、「電卓マシン」への入力も、 同じテープ上に書き込みます 。
その全てのテープを読み込むと、元々のチューリングマシンである電卓マシンと同じ結果を出力するチューリングマシン が作れると思いませんか?

万能チューリングマシン とは、 任意の入力に対して、任意のチューリングマシンの動きをシミュレートすることができるチューリングマシン です。

実は、 私たちが普段使っているPCは、万能チューリングマシンであることが知られています(もちろん、テープは読み取りません)。

このチューリングの理論を基に、本物の「コンピュータ」が誕生することになります。

いかがでしたか?次回はいよいよ私たちが知っているコンピュータの話となります。

ここまで読んでいただきありがとうございました。