Contents
概要
チューリングマシンは、1936年にイギリスの数学者アラン・チューリング（1912-1954）が論文「計算可能数について——決定問題への応用」で提示した抽象的計算モデルである。
構成要素は極めて単純である。(1) 無限長のテープ（有限個のマスに記号が書かれる）、(2) テープを1マスずつ移動して記号を読み書きするヘッド、(3) 有限個の内部状態、(4) 「現状態と読まれた記号」に対して「書き込み記号・移動方向・次状態」を決める遷移規則表。これだけで、計算可能な全ての問題を計算できる。
発見の背景
ヒルベルトが1928年に提起した決定問題（Entscheidungsproblem）——任意の数学的命題の真偽を機械的に判定する方法はあるか——が、背景にあった。ゲーデルの不完全性定理（1931）が部分的解答を与えたが、「機械的手続き」の厳密な定義が欠けていた。
チューリングは1935年頃、ケンブリッジで散歩中に着想を得たとされる。彼は計算する人（computer、当時は職業名）が紙と鉛筆で実行する過程を抽象化し、有限状態・有限規則・無限テープの機械として定式化した。
同論文で、万能チューリングマシン——他の任意のチューリングマシンをシミュレートできる単一のマシン——を構成した。これは現代コンピュータがソフトウェアを変えるだけで異なる計算を行う原理の数学的祖型である。
さらに、停止問題（任意のプログラムが有限時間で停止するかを判定する問題）がチューリングマシンで解けないことを証明し、計算不能な問題の存在を確立した。同時期のチャーチのラムダ計算と等価であることが示され、「計算可能性＝チューリング計算可能＝ラムダ計算可能」というチャーチ＝チューリングのテーゼが成立した。
意義
チューリングマシンは、現代計算機の理論的祖型である。ノイマン型アーキテクチャ、プログラム内蔵方式、コンパイラ理論、計算複雑性理論——すべてチューリングマシンを基盤とする。
第二次大戦中、チューリングはブレッチリー・パークでドイツのエニグマ暗号解読に決定的貢献をし、実践的計算機の開発を主導した。1950年の論文「計算機械と知能」では、チューリングテストを提案し、人工知能の哲学的基礎も築いた。
現代への示唆
抽象化の力
テープ・ヘッド・状態という極端な抽象化が、計算のすべてを包摂した。過剰に単純化した表現が、かえって普遍性を獲得する例である。事業モデルの抽象化も、細部を削ぎ落とすほど他事業への転用可能性が見えてくる。
不可能性の証明
停止問題の決定不能性は、「どんな天才プログラマでも解けない問題がある」という原理的不可能性の証明だった。プロジェクト判断でも、「努力すれば解ける」と「原理的に解けない」の区別が、資源配分の精度を決める。可能性と不可能性を見極める知性が、持続的組織能力となる。
汎用性という発明
万能チューリングマシンのアイデアは、ハードウェアを固定してソフトウェアで機能を変えるという現代コンピュータの根本思想を準備した。組織でも、汎用プラットフォームに機能を載せる設計と、専用ハードの最適化のバランスが、スケーラビリティと効率のトレードオフを決める。
関連する概念
- ゲーデル不完全性定理
- ノイマン型アーキテクチャ
- シャノン情報理論
- チューリングテスト
- 停止問題
参考
- A.チューリング「計算可能数について」（邦訳：伊藤和行編『チューリング——コンピュータ理論の起源』近代科学社、2014）
- A.ホッジス『エニグマ アラン・チューリング伝』勁草書房、2015
- 高橋秀俊『チューリング機械を作ってみよう』岩波科学ライブラリー