チューリングマシンと計算可能性

1. 計算のモデル：チューリングマシン（Turing Machine）

1936年、コンピュータがまだこの世に影も形もなかった時代、イギリスの数学者アラン・チューリングは、「計算する」という人間の行為をシンプルに抽象化した仮想の機械モデル「チューリングマシン」を考案しました。

その構造は単純です。

• テープ（メモリ）： 1マスごとに記号（0 や 1）が書かれた、左右に無限に長いテープ。
• ヘッド（CPU）： テープの1マスを指し示し、記号を読み書きし、テープを左右に1マス動かすヘッド。
• 状態遷移表（プログラム）： 「現在のマシンの状態がAで、テープの記号が1なら、記号を0に書き換えて、右に移動し、状態をBにせよ」といった簡単な行動ルール表。

アラン・チューリングは、この単純な機械モデルが、「すべてのコンピュータの処理能力の本質的な限界と同じである」ことを証明しました。 現代のスーパーコンピュータやスマートフォンも、複雑な回路を持っていますが、論理的にはこのチューリングマシンと処理できる能力の限界は同じです。

2. 計算不可能問題

チューリングは、チューリングマシンの限界を追究する中で、「数学的・論理的に正しい問いであっても、それを解くアルゴリズム（プログラム）を作成できない問題」が存在することを発見しました。 これを計算不可能問題（Undecidable Problem）と呼びます。

その代表的な例が、歴史的に名高い停止性問題（Halting Problem）です。

3. 停止性問題のパラドックス

停止性問題とは、以下のような問いです。

チューリングは、「そのような判定プログラムHは、存在しない（作れない）」ことを背理法（矛盾を導く証明法）を用いて証明しました。

証明のエッセンスは、嘘つきのパラドックス（「私は嘘つきである」という文が真か偽か）と全く同じです。

もし、判定プログラムHが作れると仮定します。 このHを利用して、以下のようなあまのじゃくな動作をするプログラム「天邪鬼（あまのじゃく）」を作ります。

天邪鬼は、Hが「お前は停止する」と判定したら、わざと「無限ループ」に入ります。
Hが「お前は無限ループする」と判定したら、わざと「即座に停止」します。

では、この「天邪鬼」自身を、判定プログラムHに入力したら何が起きるでしょうか？

• Hが「天邪鬼は停止する」と判定した場合：天邪鬼はルールに従って無限ループするため、Hの判定はハズレです。
• Hが「天邪鬼は無限ループする」と判定した場合：天邪鬼はルールに従って停止するため、やはりHの判定はハズレです。

どのように判定しても必ずHの判定結果と矛盾（パラドックス）が発生します。 この矛盾の原因は、「判定プログラムHが存在する」と仮定したこと自体にあります。したがって、そのようなプログラムHは数学的に存在し得ないことが証明されました。

この発見は、「コンピュータは万能ではない。数学的に厳密に定義された問題であっても、アルゴリズムによって解くことができない領域がある」という計算の限界を示した、コンピュータサイエンスにおける重要な結果です。

最後のセクションでは、「解くことはできるが、膨大な時間がかかるため実質的に解けない問題」の限界を示す、現代のコンピュータサイエンスにおける重要な未解決問題「P ≠ NP予想」について学びます。