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

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は数学的にこの宇宙に存在し得ないことが完全に証明されました。

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

最後のセクションでは、「解くことはできるが、宇宙が終わるほどの時間がかかるため実質的に解けない問題」の限界を示す、現代数学・CS最大の未解決問題「P ≠ NP予想」について学びます。