MENU

チューリングマシン

I. チューリングマシン入門：計算の抽象モデル

A. チューリングマシンの定義：概念的概観

チューリングマシン（TM）は、1936年にアラン・チューリングによって考案された、計算を記述するための数学的な抽象モデルである 1。この抽象機械は、記号が書かれたテープを一連の規則に従って操作する 1。そのモデルの単純さにもかかわらず、あらゆるコンピュータアルゴリズムを実装する能力を持つとされている 1。チューリングが「自動機械（automatic machines）」と名付けたこの装置は、特に実数の計算のために考案されたものであり、その根底には、何が計算可能であるかの範囲と限界を探求するという目的があった 3。

チューリングマシンは、形式的な記号操作の組み合わせと繰り返しで構成される全ての計算を実行することができる、最も単純化されたコンピュータのモデルとして知られている 4。この定義は、TMが計算の本質を捉えるための最小限の要素で構成されていることを示唆している。その単純な構造と普遍的な計算能力という二重性は、計算の限界を厳密に議論するための基礎を提供する。

B. 主要構成要素とその機能：テープ、ヘッド、有限制御部

チューリングマシンは、以下の主要な構成要素から成る。

  • テープ (Tape)：無限に長い帯状のもので、個々のセル（マス目）に区切られている。各セルにはただ一つの記号を記録できる 3。これは機械の記憶装置に相当し、その容量に制限はない。テープは初期状態では空白であるか、入力記号が書かれている 3。チューリングの最初のモデルでは片方向に無限なテープが用いられたが 3、両方向に無限なテープなど、様々な変種が存在する。
  • ヘッド (Head)：テープ上の一つのセルを読み取り、そのセルに新しい記号を書き込み、テープ上を左または右に一セル分移動することができる装置である 3。ヘッドは、テープと相互作用する機械の能動的な部分である。
  • 有限制御部 (Finite Control) または状態レジスタ (State Register)：TMの「頭脳」であり、有限個の内部状態（チューリングの用語ではm-configuration）のいずれかを取る 3。現在の状態とヘッドが読み取った記号によって、機械の次の動作が決定される。
  • 遷移関数 (Transition Function) または規則の表 (Table of Rules)：TMの挙動を規定する。現在の状態とヘッド下の記号が与えられると、以下の三つを指定する。
  1. テープに書き込む記号
  2. ヘッドの移動方向（左：L、右：R、または移動なし：N）
  3. 有限制御部の次の状態 1。
  • アルファベット (Alphabet)：テープに書き込むことができる記号の有限集合。これには特別な「空白」記号が含まれる 3。チューリングはまた、計算された数列を構成する「数字 (figures)」と、記憶を助けるための第二種の記号（E-squares）という、二種類の記号を用いる機械も考察した 3。

これらの構成要素は、TMが機械的でありながら抽象的な性質を持つことを強調する。無限長のテープは、有限オートマトンとは異なる、その理論的な計算能力の鍵となる。有限制御部と遷移関数は、機械の「プログラム」を定義する。TMは、記憶（テープ）、処理能力（ヘッドと有限制御部）、そしてプログラム（遷移関数）という、計算に必要不可欠な要素のみで構成されている。この最小限の構成は制限ではなく、むしろ計算そのものの厳密な数学的分析を可能にする強みである 1。このような単純なモデルが万能な計算能力を達成できるという事実は、極めて深遠な結果と言える。

以下に、チューリングマシンの主要構成要素をまとめる。これは、抽象的な概念をより具体的に理解する助けとなるだろう 5。

構成要素説明機能現実のコンピュータにおける類似物 5
テープ記号を記録できる無限長のマス目の列データの記憶と作業領域無限のノート
ヘッドテープ上の1マスを読み書きし、左右に移動テープ上の記号の読み取り、書き込み、およびアクセスのための移動ノート上を動く鉛筆
有限制御部機械の現在の状態を保持し、遷移規則に基づいて次の動作を決定する「頭脳」機械全体の動作制御、状態遷移の管理計算を進める司令塔、計算機の脳
遷移関数現在の状態と読み取った記号に基づき、次に書き込む記号、ヘッドの移動方向、次の状態を定義機械の「プログラム」であり、具体的な計算手順を規定する動作規則の集合

C. 動作の仕組み：状態遷移とテープ操作

チューリングマシンは、離散的な時間ステップで動作する 5。各ステップにおいて、以下の処理が順次実行される。

  1. ヘッドが現在位置するテープ上のセルの記号を読み取る 5。
  2. 有限制御部の現在の状態と読み取られた記号に基づき、遷移関数が次の動作を決定する 5。
  3. 機械は、スキャンされたセルに新しい記号（読み取った記号と同じ場合もある）を書き込む 3。
  4. ヘッドが左（L）、右（R）に一セル分移動するか、現在位置に留まる（N） 3。
  5. 有限制御部が新しい状態（現在の状態と同じ場合もある）に遷移する 3。

計算は、TMが指定された「停止状態」に入るか、現在の状態と記号の組み合わせに対して遷移が定義されていない場合に終了する 4。機械が停止したときにテープ上に残された記号列が、その計算の出力となる 4。標準的なチューリングマシンの各ステップは決定論的である。つまり、機械の現在の状態と観測された記号によって、その動作（記号の書き込み、ヘッドの移動、次の状態）は一意に決定される 3。この決定論的な性質は、古典的なTMモデルの基本であり、その挙動を理解し、後に非決定性TMと比較する上で極めて重要である。機械の各構成（configuration）は、正確に一つの次の構成へと導かれる。この予測可能性こそが、TMの計算を正確に追跡し分析することを可能にする。

D. 具体例：単純なチューリングマシンの動作

抽象的な概念を具体的に理解するために、テープ上の「1」の個数が偶数か奇数かを判定する単純なTMの例を示す 8。この例では、TMが特定の計算タスクを実行するように設計できることを示す。

このTMは以下のように定義される（8に基づく簡略化）。

  • 状態集合 Q: {q1​ (初期状態、偶数個の1を検出), q2​ (奇数個の1を検出), q0​ (停止状態)}
  • テープアルファベット Γ: {0, 1, ␢ (空白記号)}
  • 初期状態: q1​
  • 受理（停止）状態: q0​
  • 遷移関数 δ: Q×Γ→Q×Γ×L,R,N

以下に、このTMの遷移関数の一部を示す。

現在の状態読み取り記号次の状態書き込み記号ヘッド移動
q1​1q2​␢R
q2​1q1​␢R
q1​0q1​␢R
q2​0q2​␢R
q1​␢q0​1N
q2​␢q0​0N

動作例：入力テープ “0110␢” (ヘッドは最初の’0’の上)

  1. 状態 q1​、読み取り ‘0’。規則 (q1​, 0) → (q1​, ␢, R) により、’0’を␢に書き換え、ヘッドを右へ。テープ: “␢110␢”、状態 q1​。
  2. 状態 q1​、読み取り ‘1’。規則 (q1​, 1) → (q2​, ␢, R) により、’1’を␢に書き換え、ヘッドを右へ。テープ: “␢␢10␢”、状態 q2​ (1の個数が奇数)。
  3. 状態 q2​、読み取り ‘1’。規則 (q2​, 1) → (q1​, ␢, R) により、’1’を␢に書き換え、ヘッドを右へ。テープ: “␢␢␢0␢”、状態 q1​ (1の個数が偶数)。
  4. 状態 q1​、読み取り ‘0’。規則 (q1​, 0) → (q1​, ␢, R) により、’0’を␢に書き換え、ヘッドを右へ。テープ: “␢␢␢␢␢”、状態 q1​。
  5. 状態 q1​、読み取り ‘␢’。規則 (q1​, ␢) → (q0​, 1, N) により、’␢’を’1’に書き換え、ヘッドは移動せず、状態 q0​へ。テープ: “␢␢␢␢1″、状態 q0​。
  6. 状態 q0​は停止状態なので、計算は終了。テープ上の出力は ‘1’ であり、入力中の ‘1’ の個数（2個）が偶数であったことを正しく示している。

このような具体例は、TMの動作を明確に示し、抽象的な定義にもかかわらず特定の計算タスクを実行できることを示す 7。

II. アラン・チューリングと機械の創世

A. アラン・チューリング：現代計算機の設計者

アラン・マシスン・チューリング（Alan Mathison Turing, 1912年-1954年）は、イギリスの数学者、論理学者、暗号解読者であり、理論計算機科学および人工知能の父として広く認識されている 10。彼は早くから知的な才能を発揮し、ケンブリッジ大学キングス・カレッジで学び、そこで計算可能性の理論を研究した 10。

第二次世界大戦中、チューリングはブレッチリー・パークでドイツ軍の暗号、特にエニグマ暗号の解読に中心的な役割を果たし、戦争の結果に大きな影響を与えたと評価されている 10。彼の貢献は戦争終結を早めた英雄的行為と称される一方で、その生涯は同性愛に対する当時の法的な迫害により悲劇的な側面も持つ 10。彼の業績は、純粋数学の理論的研究から、国家の安全保障に直結する実践的な問題解決まで多岐にわたる。この理論と実践の融合は、チューリングの仕事の顕著な特徴である。計算可能性という抽象的な概念に関する彼の初期の研究 13は高度に理論的であり、論理学の根本的な問いに動機づけられていた。しかし、その後の暗号解読作業 10は強烈な実践的要請に応えるものであり、現実世界に計り知れない影響を及ぼした。TM概念の構築に必要とされた抽象的思考能力は、暗号解読という複雑な問題に取り組む上で役立った可能性があり、逆に、戦時下の問題解決の緊急性は、効果的で「機械的な」手順の価値を強固にしたかもしれない。これは、彼の理論的探求と応用的仕事の間に相互補完的な関係があったことを示唆している。

B. 知的背景：ヒルベルトの決定問題と「機械的手順」の探求

チューリングマシンの概念は、当時の数学界における重要な未解決問題、特にダフィット・ヒルベルトによって提起された「決定問題（Entscheidungsproblem）」と深く関連している。ヒルベルトは1900年に23の数学上の問題を発表し 15、その後1928年には、与えられた任意の数学的命題あるいは論理式が真か偽かを常に決定できるような一般的な「機械的手順」またはアルゴリズムが存在するかどうかを問う決定問題を提起した 16。これは、あらゆる数学的問題を自動的に「解ける」一般的な手法があるかどうかを問うものであった 16。

ヒルベルトの第10問題（ディオファントス方程式の可解性の決定）もまた、特定の決定問題であり、後にユーリ・マチャセビッチによって否定的に解決されたが、この結果も計算可能性理論と関連している 15。チューリングの計算可能数とTMに関する研究は、この決定問題に取り組むために、「機械的手順」という概念に厳密な形式的定義を与えることを直接の目的としていた 17。

ヒルベルトによる「機械的手順」の探求 16は、そのような手順が何を意味するのかという正確な定義を暗黙のうちに要求していた。チューリング（および同時期のアロンゾ・チャーチ）以前には、「アルゴリズム」や「有効な計算」について、広く受け入れられた厳密な定義は存在しなかった。「機械的手順」という言葉の曖昧さが、問題解決の障壁となっていたのである。チューリングマシンは、この欠けていた形式化を提供した 17。したがって、決定問題は、特定の答え（チューリングが示したように否定的）を導き出しただけでなく、より重要なことに、計算の定義を強いることによって、計算機科学の理論的基礎そのものの創造を触発したのである。

C. チューリングの1936年の画期的論文：「計算可能数について、決定問題への応用を伴って」

1936年から1937年にかけて発表された論文「計算可能数について、決定問題への応用を伴って（On Computable Numbers, with an Application to the Entscheidungsproblem）」3において、チューリングはチューリングマシン（彼自身は「自動機械」または「a-machine」と呼んだ）の概念を導入した 3。この論文の主目的は、「計算可能数」（その十進表現が有限の手段によって計算可能な実数）を定義し、それを通じて「計算可能関数」を定義することであった 3。

決定的に重要なのは、チューリングがこの形式化を用いて、決定問題が決定不可能であること、すなわち、そのような一般的な機械的手順は存在しないことを証明した点である 16。彼は、特定の記号をTMが出力するかどうか、あるいはTMが停止するかどうかといった問題が、いかなるTMによっても解決できないことを示し、これを決定問題に関連付けることで証明を達成した 19。この論文はまた、他のいかなる計算機械をも模倣できる「万能計算機械（universal computing machine）」の概念も導入した 3。

この論文は計算機科学の基礎文献の一つであり、TMを導入しただけでなく、決定不可能な問題の最初の明確な例とその厳密な証明を提供した。チューリングの論文以前、ヒルベルトのプログラムに代表されるように、数学においては、原理的には全ての数学的問題がアルゴリズム的に解決可能であるという楽観論が支配的であった。チューリングによる決定問題の決定不可能性の証明 16は、この信念を打ち砕いた。それは、機械的手順によって知りうることには本質的な限界があることを示したのである。これは単なる数学的結果ではなく、形式システム、ひいてはアルゴリズム的手法に限定された人間の理性の力と限界についての我々の理解を再形成する哲学的な結果でもあった。自己参照と矛盾に関連して証明不可能な問題が存在することに言及する資料もあり 20、この哲学的転換を示唆している。

III. 計算可能性の理論：計算の境界の定義

A. 「計算可能」とは何を意味するのか？：チューリングによる形式化

チューリングによる計算の分析は、人間が紙と鉛筆を使って計算を行う「計算手（computor）」の行動をモデル化することを含んでいた 19。彼はこのプロセスを、機械が実行可能な単純で離散的なステップに分解した。ある数が「計算可能」であるとは、その十進表現がTMによって書き出されることができる場合を指す 3。関数が「チューリング計算可能」であるとは、その関数の引数を表す入力を与えられたときに、テープ上に関数の出力を残して停止するTMが設計できる場合を指す 3。

これにより、「有効に計算可能」あるいは「アルゴリズム的」といった直感的な概念に対して、正確で数学的な定義が与えられた 11。計算可能性の理論は、どの問題がそのような機械的プロセスによって解決可能であり、計算可能な問題のクラスがどのような構造的特性を持つかを研究する分野である 11。この形式化は画期的であり、「計算可能性」を数学的な対象として研究することを可能にし、アルゴリズムの性質に関するより深い理解へと繋がった。

チューリングの分析が人間の計算手の行動に明示的に焦点を当てていたという事実は重要である 19。TMは人間の計算手の行動を模倣するように設計され、その制約は人間の限界（有限の精神状態、限られた観測範囲）から導き出された。これは、TMが単なる抽象的な数学的構成物ではなく、人間のアルゴリズム的思考のプロセスそのものをモデル化しようとする試みであることを意味する。これを形式化することによって、チューリングは機械を構築するための道具だけでなく、ある種の人間知性の活動の限界を理解するための道具をも提供したのである。

B. チャーチ＝チューリングのテーゼ：計算機科学の基本信条

チャーチ＝チューリングのテーゼ（CTT）は、直感的に「有効に計算可能」または「アルゴリズム的」であると考えられるあらゆる関数は、チューリングマシンによって計算可能であると主張する 5。同時期に、アロンゾ・チャーチはラムダ計算を用いて同様の考えを独立して提唱した 11。これらの形式化や再帰関数といった他の形式化との等価性は、CTTに対する強力な支持となった。

CTTは数学的な定理として証明できるものではない（なぜなら「直感的に計算可能」という概念が形式的な定義ではないため）。むしろ、広範な証拠と反例が見つかっていないことに基づく、広く受け入れられている仮説である 11。その意義は、計算とは何かという安定した形式的定義を提供することにある。これは、TMモデルが考えうるあらゆるアルゴリズム的プロセスの完全な能力を捉えていることを示唆する。もしある問題がTMによって決定不可能であれば、それはあらゆるアルゴリズム的手段によって決定不可能であると考えられる 5。CTTは理論計算機科学の礎石であり、TMの限界について語るとき、我々が計算そのものの根本的な限界について語っているという確信を与えてくれる。

チューリングマシンモデルの堅牢性は、CTTの証拠として機能する。複数のテープを持つTMや高次元のテープを持つTMなど、より強力な計算モデルを作成しようとする様々な試みは、すべて標準的なTMと同等の計算能力を持つモデルに帰着することが示されている 11。これらのモデルは標準的なTMでシミュレート可能なのである。この堅牢性、すなわち多くの異なる、一見より強力に見える形式化がTMと等価であることが判明するという事実は、TM（ひいてはラムダ計算など）が計算に関する何か根本的で普遍的なものを捉えていることを強く示唆しており、CTTに強力な信頼性を与えている。

IV. 万能チューリングマシン：全機械を模倣する機械

A. 万能計算の概念

アラン・チューリングは、単一のTMでありながら、他のいかなるTMの挙動をも模倣（シミュレート）することができる「万能チューリングマシン（Universal Turing Machine, UTM）」の存在を証明した 3。UTMは入力として以下の二つを取る。

  1. 模倣されるTM（Mとする）の記述（またはプログラム）。
  2. Mのための入力データ 3。

そしてUTMは、Mをステップバイステップでシミュレートし、Mが生成したであろう同じ出力を生成する 22。これは深遠な概念である。原理的には、一つの機械が、適切な指示を与えられれば、特定のタスクのために設計された他のいかなる機械の仕事も実行できることを意味する。これは汎用コンピュータの理論的基礎である。

B. 万能チューリングマシンのアーキテクチャと操作

他のTM（M）をシミュレートするために、UTMはMの記述（その状態、アルファベット、遷移関数）とMの現在の構成（テープ内容、ヘッド位置、現在の状態）を自身のテープ上に表現する方法を必要とする 3。チューリングは、任意のTMのための「標準記述（Standard Description, S.D.）」または符号化方式を開発し、それによってTMを記号の文字列として表現できるようにした 3。この符号化された記述は、しばしばMの「プログラム」と呼ばれる。

UTMのテープは通常、いくつかのセクションに分割される。一つはMの符号化された記述のため、もう一つはMのシミュレートされたテープのため、そして場合によっては自身の計算のための作業領域である 3。

UTMの操作は以下の手順を含む。

  1. 自身のテープからMの現在の状態とMのシミュレートされたヘッド下の記号を読み取る。
  2. Mの符号化された記述を参照して、適切な遷移規則を見つける。
  3. Mの規則に従って、自身のテープ上のMのシミュレートされたテープ、ヘッド位置、状態を更新する 3。
  4. このプロセスを繰り返す。

UTMの能力は、他の機械（M）の記述をデータとして扱い、それを実行するという点に本質がある 3。これはソフトウェアの基本的な考え方そのものである。Mの記述はプログラムに類似し、UTMはそのプログラムを実行するハードウェアに類似する。UTM以前は、各TMは「専用機械」であった（例えば、乗算専用のTMが言及されている 18）。UTMは、異なる「プログラム」（他のTMの記述）をロードすることによって異なるタスクを実行できる単一の固定機械という概念を導入した。この固定機械（ハードウェア）と可変な命令（ソフトウェア）の分離は、現代のコンピューティングの礎石である。

C. UTM：プログラム内蔵方式コンピュータの理論的先駆け

UTMの概念、すなわち「プログラム」（シミュレートされるTMの記述）がテープ上に格納され、UTMによってデータとして扱われるという考え方は、現代のコンピュータにおけるプログラム内蔵方式（stored-program concept）の直接的な理論的先行概念である 3。EDVACのような初期の電子計算機の開発における重要人物であるジョン・フォン・ノイマンは、チューリングの研究を知っており、その影響を受けていた 3。プログラム内蔵方式アーキテクチャにより、コンピュータは物理的な再配線なしにメモリから異なるプログラムをロードして実行する汎用性を獲得した。

UTMとプログラム内蔵方式コンピュータの間の最も重要な繋がりは、プログラムの命令自体がデータとして符号化され、別のプログラム（UTM自身またはコンピュータのCPU）によって操作され得るという考え方である。UTMが他のTMの記述（それは他のデータと同様にテープ上に格納される）を操作するという事実は 3、この点を明確に示している。プログラムとデータの間の境界線を曖昧にするこの考え方は革命的であった。それは、プログラムが他のプログラムによって作成、変更、実行され得ることを意味し、ソフトウェア工学、コンパイラ、オペレーティングシステムなどの全分野へと繋がった。

V. 計算不能性：停止性問題による限界の探求

A. 決定不可能性入門

TMの能力（そしてCTTによれば、あらゆるアルゴリズム的プロセスの能力）にもかかわらず、チューリングはいかなるTMも解決できない数学的に明確に定義された問題が存在することを示した 20。これらは「決定不可能（undecidable）」または「解決不可能（unsolvable）」な問題と呼ばれる。これは、全ての可能な入力に対して、有限時間内に正しく答え（はい/いいえ）を決定できるアルゴリズムが存在しないことを意味する。これは画期的な発見であり、計算に対する根本的な限界を明らかにした。それはヒルベルトの決定問題に否定的な答えを与えた。

B. 停止性問題：プログラムが停止するかを予測できるか？

停止性問題とは、任意のTM（またはプログラム）Mと入力wが与えられたとき、Mがw上で実行された場合に最終的に停止するか、それとも永遠に実行し続ける（例えば無限ループに陥る）かを決定する問題である 27。チューリングは、停止性問題が決定不可能であることを証明した 27。これは、全ての可能なTMと入力のペアに対して停止性問題を正しく解決できる単一の一般的なアルゴリズム（TM）は存在しないことを意味する 28。停止性問題は、決定不可能な問題の典型例であり、その決定不可能性は計算機科学、特にプログラム検証や人工知能の分野に深遠な影響を与える。

C. 停止性問題の決定不可能性の証明：対角線論法による

この証明は通常、カントールの対角線論法に類似した技法を用いた背理法によって行われる 27。

  1. ステップ1（背理法のための仮定）：
    まず、停止性問題を解決するTM、Halt(P, I)が存在すると仮定する。Halt(P, I)はプログラムPの記述と入力Iを受け取り、PがI上で停止するならば「停止する」を出力し、PがI上で永遠に実行されるならば「ループする」を出力する 28。
  2. ステップ2（矛盾した機械の構築）：
    次に、この仮定されたHaltを用いて、新たなTM Paradox(X)を構築する。Paradox(X)はTM Xの記述を入力として受け取り、以下のように動作する。
  1. Halt(X, X)を実行する（つまり、プログラムXが自身の記述を入力として実行された場合に停止するかどうかをHaltに問い合わせる）。
  2. もしHalt(X, X)が「停止する」と出力した場合、Paradox(X)は意図的に無限ループに入る。
  3. もしHalt(X, X)が「ループする」と出力した場合、Paradox(X)は停止する（例えば0を出力して）28。
  4. ステップ3（矛盾の導出）：
    Paradoxを自身の記述を入力として実行した場合、すなわちParadox(Paradox)を実行した場合、何が起こるか？
  • ケース1：Paradox(Paradox)が停止すると仮定する。 Paradoxの定義によれば、これが起こり得るのはHalt(Paradox, Paradox)が「ループする」と出力した場合のみである。しかし、Haltが正しい判定機であるならば、Halt(Paradox, Paradox)が「ループする」と出力することは、Paradox(Paradox)が永遠にループすることを意味する。これは矛盾である。
  • ケース2：Paradox(Paradox)が永遠にループすると仮定する。 Paradoxの定義によれば、これが起こり得るのはHalt(Paradox, Paradox)が「停止する」と出力した場合のみである。しかし、Haltが正しい判定機であるならば、Halt(Paradox, Paradox)が「停止する」と出力することは、Paradox(Paradox)が停止することを意味する。これもまた矛盾である 28。
  1. ステップ4（結論）：
    どちらの可能性も矛盾に至るため、最初の仮定、すなわち停止性問題を解決できるTM Haltが存在するという仮定は偽でなければならない。したがって、停止性問題は決定不可能である 28。

この証明は、計算可能性理論における自己参照と対角線論法の力を示す古典的な例である。停止性問題の決定不可能性の証明は、Paradoxという機械がそれ自身に関する予測に基づいて動作するように構築される点に核心がある 28。計算プロセスが自身の記述や挙動を分析または参照するという、この自己参照は、決定不可能性や計算不能性において繰り返し現れるテーマである 20。これは、集合論におけるラッセルのパラドックスやゲーデルの不完全性定理に類似している。TM（特にUTM）が他のTM（自身を含む）の記述を操作できる能力は、これらの種類のパラドキシカルな構成への扉を開き、固有の限界を明らかにする。

D. 決定不可能な問題の広範な含意

停止性問題のような決定不可能な問題の存在は、以下のことを意味する。

  • 完全なプログラム検証（例えば、任意の与えられたプログラムが全ての入力に対して無限ループに陥らないことを証明すること）は、一般的には不可能である。
  • プログラムの挙動に関する特定の問いには、アルゴリズム的に答えることができない。
  • これは、人工知能、自動定理証明、形式手法の限界に影響を与える。

数学や計算機科学における他の多くの問題（ポステの対応問題、ヒルベルトの第10問題のアルゴリズム的解法など）も、停止性問題と等価であるか、または停止性問題に帰着できることを示すことによって、決定不可能であることが証明されている。決定不可能性は単なる理論的好奇心ではなく、我々がコンピュータに期待できることとできないことに関して実践的な帰結をもたらす。

停止性問題の決定不可能性は、我々の現在の巧妙さの欠如や不十分な計算能力によるものではない。それは、チューリングマシンモデル（そしてCTTによれば、あらゆる等価なモデル）によって捉えられるアルゴリズムの性質に関する根本的な数学的真理である 27。これは、技術がいかに進歩しても、それがアルゴリズム的原理に基づいて動作する限り、これらの限界は残ることを示唆している。この点が、単に計算困難（手に負えない）だが理論的には解決可能な問題と決定不可能性を区別する。

VI. 形式言語とオートマトン理論におけるチューリングマシン

A. チューリングマシンの変種：多テープ、非決定性、その他

標準的なTMモデルのいくつかの変種が提案されている。

  • 多テープTM (Multi-tape TMs)：それぞれ独自のヘッドを持つ複数のテープを有する。これらは一部のTMの設計を単純化することができる 25。
  • 非決定性TM (Non-deterministic TMs, NTMs)：遷移関数が、与えられた状態と記号に対して複数の可能な次の動作を指定できる。NTMは、少なくとも一つの選択肢の系列が受理状態に至る場合に入力を受理する 32。
  • 両方向無限テープを持つTM 25。
  • 制限付きTM（例：読み取り専用テープ、一度だけ書き込み可能なテープ）25。

これらの変種の多く（多テープTMやNTMを含む）は、標準的な単一テープの決定性TMと計算能力において等価であることが証明されている 25。これは、変種TMによって実行可能なあらゆる計算は、標準TMによっても実行可能であり、その逆もまた同様であることを意味する（ただし、変種の方が特定のタスクに対してステップ数やプログラムの容易さの点で効率的な場合がある）。例えば、多テープTMは、単一テープをトラックに分割したり、複数テープの内容を交互に配置したりすることによって、単一テープTMでシミュレートできる 25。NTMは、NTMの計算の木構造を幅優先探索するなどして、可能な全ての計算経路を系統的に探索することによってDTMでシミュレートできる 25。

これらの等価性の結果は、TMモデルの堅牢性とチャーチ＝チューリングのテーゼを補強する。それらは、計算可能性の基本的な定義が、これらの種類のアーキテクチャの詳細に影響されないことを示している。多テープTMや非決定性TMのような変種は、基本的な計算能力を増大させないが 25、特定のアルゴリズムを記述したり、特定の計算現象（NTMにおける並列探索など）をモデル化したりするための、より便利で自然な方法を提供することが多い。標準TMは、その最小限性ゆえに、計算可能性の限界に関する理論的証明に理想的である。変種は、計算量を研究したり、わずかに高い抽象度でアルゴリズムを設計したりするのに有用であり、それらが常に標準モデルに帰着できることを知った上で利用される。これは科学における共通のテーマ、すなわち当面の問題に適した抽象度のレベルを選択するということを浮き彫りにする。

B. チョムスキー階層：チューリングマシンの位置付け（タイプ0）

ノーム・チョムスキーによって1956年に提案されたチョムスキー階層は、形式文法とそれらが生成する言語を4つの主要なタイプ（タイプ0からタイプ3）に分類する 37。各タイプの文法は、その文法によって生成される言語を認識できるオートマトンのクラスに対応している。

  • タイプ0（制限のない文法 Unrestricted Grammars）：帰納的可算言語（Recursively Enumerable Languages）を生成する。チューリングマシンによって認識される 38。
  • タイプ1（文脈依存文法 Context-Sensitive Grammars）：文脈依存言語（Context-Sensitive Languages）を生成する。線形拘束オートマトン（Linear Bounded Automata, LBAs）によって認識される 38。
  • タイプ2（文脈自由文法 Context-Free Grammars）：文脈自由言語（Context-Free Languages）を生成する。非決定性プッシュダウンオートマトン（Non-deterministic Pushdown Automata, PDAs）によって認識される 38。
  • タイプ3（正規文法 Regular Grammars）：正規言語（Regular Languages）を生成する。有限オートマトン（Finite Automata, FAs）によって認識される 38。

この階層は包含的であり、タイプ3言語はタイプ2の部分集合、タイプ2はタイプ1の部分集合、タイプ1はタイプ0の部分集合である 38。チョムスキー階層は、言語の複雑性と計算能力の様々なレベル間の関係を理解するための枠組みを提供する。それは、TMをこの階層の頂点に位置付け、形式的に定義された言語の最も一般的なクラスを認識できるものとして示す。

以下にチョムスキー階層をまとめる。

タイプ文法名言語クラス認識オートマトン
タイプ0制限のない文法帰納的可算言語チューリングマシン
タイプ1文脈依存文法文脈依存言語線形拘束オートマトン
タイプ2文脈自由文法文脈自由言語非決定性プッシュダウンオートマトン
タイプ3正規文法正規言語有限オートマトン

チョムスキー階層 38は単に言語を分類するだけでなく、計算モデルの増大する能力を暗黙のうちに示している。有限オートマトン（タイプ3）は現在の状態以外の記憶を持たない。プッシュダウンオートマトン（タイプ2）はスタックを追加し、入れ子構造を扱えるようにする。線形拘束オートマトン（タイプ1）は入力サイズに比例したテープを持ち、より強力だが依然として有界な記憶を表す。チューリングマシン（タイプ0）は無制限のテープを持ち、理論的な最大の計算能力を有する。この進展は、特定の資源（記憶の種類やアクセス方法など）を追加することが、オートマトンが解決できる問題のクラスをどのように増大させるかを明確に示しており、TMはアルゴリズム計算の頂点に位置する。

VII. 結論：チューリングマシンの不朽の遺産と意義

A. チューリングマシンの主要な貢献の要約

チューリングマシンは、計算の理論と実践に計り知れない影響を与えてきた。その主要な貢献は以下のように要約できる。

  • 「アルゴリズム」および「有効な計算」という直感的概念に対する最初の説得力のある形式化を提供した。
  • 計算可能なものの境界を定義する、基本的なチャーチ＝チューリングのテーゼへと繋がった。
  • 汎用的なプログラム内蔵方式コンピュータの理論的基礎である万能チューリングマシンの概念を導入した。
  • 決定不可能な問題（例：停止性問題）の存在を確立し、計算に固有の限界を明らかにした。
  • チョムスキー階層において最も強力なオートマトンとして機能し、タイプ0言語を認識する。

B. 理論計算機科学、数学、心の哲学への持続的影響

チューリングマシンの遺産は、単なる歴史的成果に留まらない。それは複数の学問分野において、今日なお不可欠な概念的道具であり続けている。

  • 理論計算機科学：計算可能性、計算複雑性理論（P対NP問題など）、アルゴリズム設計の研究において中心的なモデルであり続けている。
  • 数学：論理学における基礎的な問題（決定問題）を解決し、形式システムの限界の理解に貢献した。
  • 心の哲学：思考の本質、知能、そして人間の心が計算システムとして理解できるか否か（チューリングテストなど）に関する議論に影響を与えた 12。
  • 人工知能：TM自体はAIアーキテクチャではないが、それが基礎をなす計算の理論は、AIシステムが原理的に何ができ、何ができないかを理解する上で根本的である。

チューリングマシンは、その抽象的でありながら機械的な性質により、異なる実践共同体の間でその同一性を維持しつつも、各共同体によって異なって使用され解釈されるのに十分適応的な概念、すなわち「境界対象物（boundary object）」として機能する。数学者はそれを論理学の道具と見なし 17、計算機科学者はそれを実在の機械やアルゴリズムの基礎と見なす 3。哲学者はそれを用いて心と知能の本質を探求する 12。この学際的な橋渡し能力、すなわち形式的な数学的対象であり、物理的計算の青写真であり、そして思考のメタファーでもあるという同時性は、その不朽の力と影響力の鍵となる理由である。それは、多様な分野が共通の、しかし多面的な概念的枠組みを通じて互いに「対話」することを可能にする。

チューリングマシンはその単純さで称賛されるが 1、数学的証明の限界から人工知能の可能性、現代コンピュータの仕組みに至るまで、非常に複雑な現象をモデル化し理解するために用いられる 5。これは継続的な知的緊張を生み出す。どのようにしてこのような単純なモデルがこれほど強力であり得るのか？その答えの一部は、その抽象化にある。本質的でない詳細を取り除くことによって、計算の核となる論理に焦点を合わせる。しかし、これはまた、TMから導き出された洞察（特に決定不可能性のような限界）を複雑な現実世界のシステム（人間の脳や大規模なソフトウェアシステムなど）に適用するには、慎重な解釈とモデルによって行われた単純化に対する認識が必要であることを意味する。TMの遺産には、その直接的な結果だけでなく、この洗練された抽象化と複雑な現実との間のギャップを埋める継続的な作業も含まれる。

アラン・チューリングの先駆的な業績は、計算という行為そのものに対する我々の理解を根本から変革し、情報化時代の知的基盤を築いたと言えるだろう。チューリングマシンは、その単純さのうちに深遠な真理を秘めた、人類の知的達成の記念碑として、今後も研究と議論を刺激し続けるであろう。

引用文献

  1. en.wikipedia.org https://en.wikipedia.org/wiki/Turing_machine
  2. チューリングマシンを学ぼう！ – MaruLabo https://www.marulabo.net/docs/turingmachine/
  3. Turing Machines (Stanford Encyclopedia of Philosophy) https://plato.stanford.edu/entries/turing-machine/
  4. チューリングマシン 【Turing machine】 チューリング機械 – IT用語辞典 e-Words https://e-words.jp/w/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3.html
  5. チューリングマシン：計算の基礎 | AI用語解説 AIコンパス https://ai-compass.weeybrid.co.jp/algorizm/turing-machine-the-foundation-of-computation/
  6. チューリングとチューリングマシン 1 アラン・チューリング 2 チューリングと言語学 – 東京工業大学 – 言語学 https://cuckoo.js.ila.titech.ac.jp/~yamagen/ling/ling-turing-single2018.pdf
  7. 8. Turing 機械入門(1) https://www.jaist.ac.jp/~uehara/course/2006/ti113/11tm.pdf
  8. 情報数学 第5回 チューリング機械 https://web.sfc.keio.ac.jp/~hagino/mi17/05.pdf
  9. 万能チューリングマシンの創り方 – Qiita https://qiita.com/38912Pataro/items/ffdc549b3b8fa3c43325
  10. アラン＝チューリング 科学を作った偉人たち③ – 横浜サイエンスフロンティア受験対策セミナー https://sci-fro-seminar.com/explain-turing/
  11. 計算可能性理論 – Wikipedia https://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E6%80%A7%E7%90%86%E8%AB%96
  12. Alan Turing – Stanford Encyclopedia of Philosophy https://plato.stanford.edu/entries/turing/
  13. ainow.ai https://ainow.ai/2022/11/11/270122/#:~:text=%E3%82%A2%E3%83%A9%E3%83%B3%E3%83%BB%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%81%AE%E7%94%9F%E6%B6%AF,-1912%E5%B9%B4%E3%81%AB&text=%E5%BD%BC%E3%81%AF%E3%82%B1%E3%83%B3%E3%83%96%E3%83%AA%E3%83%83%E3%82%B8%E5%A4%A7%E5%AD%A6%E3%81%AE,%E8%A7%A3%E8%AA%AD%E3%82%92%E4%BB%BB%E3%81%95%E3%82%8C%E3%81%BE%E3%81%99%E3%80%82
  14. チューリングマシン ～コンピューター科学の巨人アラン・チューリングの論理モデル～ 後半 https://staff.persol-xtech.co.jp/corporate/security/article.html?id=31
  15. ヒルベルトの23の問題 – Wikipedia https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%AB%E3%83%99%E3%83%AB%E3%83%88%E3%81%AE23%E3%81%AE%E5%95%8F%E9%A1%8C
  16. Entscheidungs Problem｜決定問題 – TANAAKK https://www.tanaakk.com/2025/03/18/entscheidungsproblem%EF%BD%9C%E6%B1%BA%E5%AE%9A%E5%95%8F%E9%A1%8C/
  17. チューリングの歴史的位置づけを巡って https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/230670/1/phs_12_67.pdf
  18. アラン・チューリング http://kan5.sakura.ne.jp/konwa/KuramaeHandout/kuroiwa_turing-model.pdf
  19. On computable numbers, with an application to the … https://people.math.ethz.ch/~halorenz/4students/Literatur/TuringFullText.pdf
  20. Turing Machine の原理 – 東京女子大学情報処理センター https://www.cis.twcu.ac.jp/~asakawa/ANNS/Turing_Machine.html
  21. 『Small universal Turing machines』を、UTM(2, 18)について理解する – Qiita https://qiita.com/Snowman-s/items/80d69cd177c722978cdb
  22. 4 章 チューリング機械 – 電子情報通信学会知識ベース https://www.ieice-hbkb.org/files/06/06gun_02hen_04.pdf
  23. Lecture 8 – Universal turing machines – ECE374-B Archive https://ecealgo.com/lectures/Lec08.html
  24. CSE 460 Universal Turing Machine and the Simulated Turing machine https://cse.msu.edu/~pramanik/teaching/courses/cse460/12f/lectures/L8_TM/UnivTM.pdf
  25. Turing 機械の変種 Variants of Turing Machine http://iso.2022.jp/math/undecidable-problems/files/variants-of-turing-machine.pdf
  26. 現代の僕「コンピュータが生まれた歴史知りたい」 – zawawahoge’s site https://www.zawawahoge.com/science/computer-history/
  27. チューリングマシンとは？コンピューター・ソフトウェアの生みの親アラン・チューリング https://staff.persol-xtech.co.jp/corporate/security/article.html?id=30
  28. 停止性問題 – Wikipedia https://ja.wikipedia.org/wiki/%E5%81%9C%E6%AD%A2%E6%80%A7%E5%95%8F%E9%A1%8C
  29. Halting problem – Wikipedia https://en.wikipedia.org/wiki/Halting_problem
  30. CS245 Undecidability https://cs.uwaterloo.ca/~a23gao/cs245_f17/notes/undecidability_solutions.pdf
  31. 5．チューリングマシンと計算 5 チ リング シンと計算 http://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2007/note/5.pdf
  32. 非決定性チューリングマシン – Wikipedia https://ja.wikipedia.org/wiki/%E9%9D%9E%E6%B1%BA%E5%AE%9A%E6%80%A7%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
  33. 第5章チューリングマシン – Guppy https://guppy.eng.kagawa-u.ac.jp/2024/Automaton/Text/Automaton5.pdf
  34. Improved Simulation of Nondeterministic Turing Machines – University at Buffalo https://cse.buffalo.edu/faculty/regan/papers/pdf/KLRS11.pdf
  35. Nondeterministic Turing Machines https://courses.grainger.illinois.edu/cs374/sp2018/a/notes/models/09-nondeterminism.pdf
  36. DFSとBFSの計算量は違う – アルゴリズム – Qiita https://qiita.com/assy0000/items/6d0b798e9cd725f5caa9
  37. チョムスキー階層とは？ わかりやすく解説 – Weblio辞書 https://www.weblio.jp/content/%E3%83%81%E3%83%A7%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%BC%E9%9A%8E%E5%B1%A4
  38. チョムスキー階層 – Wikipedia https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A7%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%BC%E9%9A%8E%E5%B1%A4
  39. プッシュダウン・オートマトン – Wikipedia https://ja.wikipedia.org/wiki/%E3%83%97%E3%83%83%E3%82%B7%E3%83%A5%E3%83%80%E3%82%A6%E3%83%B3%E3%83%BB%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3
  40. ほんとうに「ゼロから」理解する P ≠ NP 問題 #アルゴリズム – Qiita https://qiita.com/reika727/items/de2d345d352f951e8924
用語集