チューリングマシンのソースを表示

{{出典の明記|date=2011年12月}}
[[ファイル:Turingmachine.jpg|thumb|right|220px|チューリングマシン]]
'''チューリングマシン '''({{lang-en-short|Turing machine}}) は、[[アラン・チューリング]]が「[[計算可能性理論|計算可能性]]」に関する議論のために提示した[[抽象機械]]である<ref>{{Cite Kotobank |word=チューリングマシン |encyclopedia=ASCII.jpデジタル用語辞典 |accessdate=2022-02-02}}</ref>。

== 歴史 ==
[[アラン・チューリング|チューリング]]の「計算可能数について──[[決定問題]]への応用」（1936年）において提示された<ref>{{Cite journal|last=Turing|first=A. M.|date=1937|title=On Computable Numbers, with an Application to the Entscheidungsproblem|url=http://doi.wiley.com/10.1112/plms/s2-42.1.230|journal=Proceedings of the London Mathematical Society|volume=s2-42|issue=1|pages=230–265|language=en|doi=10.1112/plms/s2-42.1.230}}</ref>。同様なものを同年に[[エミール・ポスト]] (Emil Post) も独立に発表している<ref>{{Cite journal |author=Post, Emil L |year=1936 |url=https://doi.org/10.2307/2269031 |title=Finite combinatory processes—formulation |journal=The journal of symbolic logic |volume=1 |issue=3 |pages=103-105 |publisher=Cambridge University Press |doi=10.2307/2269031}}Reprinted in ''The Undecidable'', pp. 289ff.</ref>。構想の理由、動機についてはポストの論文が明確だが、機械自体に関する記述はチューリングの論文が詳細である。次いで、同時代に提示された他の[[計算モデル]]も[[計算可能性理論|計算可能性の理論]]からは同等であることが確認され、[[チャーチ＝チューリングのテーゼ|チューリング＝チャーチのテーゼ]]はそれらを「計算可能」の定義とすることを提唱した。

== 概要 ==
ここでは非形式的（直感的）に述べる。理論的には形式的に述べる必要がある。

チューリングマシンには、いわゆるハードウェアに相当するものとして、
# その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる<ref group="注">一般的には両方向にいくらでもシークできるものとするが、理論的には片方には端があっても良いのでそのように制限することもある。</ref>）とする
# テープに記号を読み書きするヘッド
# ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、[[有限オートマトン]]
がある。

また、ソフトウェアに相当するものとして、以下がある。
# テープに読み書きされる有限個の種類の記号
#  最初から（初期状態において）テープにあらかじめ書かれている記号列
#有限オートマトンの状態遷移規則群。詳細は次で述べる
この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」（内部状態）と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。
* テープの「現在の場所」に新しい記号を書き込む（あるいは、現在の記号をそのままにしてもよい）
* ヘッドを右か左に一つシークする（あるいは、移動しなくてもよい）
* 有限オートマトンを次の状態に状態遷移させる（同じ状態に遷移してもよい）
さらに、この有限オートマトンには（一般的な有限オートマトンの「受理状態」と同様な）「受理状態」がある。[[計算可能性理論]]的には、[[決定問題]]の2種類の答えに対応する、2種類の受理状態が必要である<ref group="注">あるいは単に停止する場合は、停止する前に、答えがどちらであるかを、テープ上の記号列として書き残してから停止する。</ref>。

== 現実の計算との関係 ==
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、[[アルゴリズム]]をチューリング機械上の手続きと同一視して議論することができる（[[チャーチ＝チューリングのテーゼ]]）。

数学の[[形式体系]]はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない（[[停止性問題]]）。これは[[ゲーデルの不完全性定理]]の別の表現の形とみなすことができる。

== 形式的な定義 ==
<!--「形式的」というのはこの分野の専門用語であり、少なくともこの節において専門用語的に正確でない「厳密」という表現を使うのは間違い-->この節では、チューリングマシンを形式的（formal）に記述する。

; チューリングマシン
: チューリングマシン {{mvar|M}} は次の7つ組で定義される：
: <math display="block">M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle\,.</math>
; 状態
: [[有限集合]] {{mvar|Q}} の[[元 (数学)|元]] {{math2|1=''q'' &isin; ''Q''}} を'''状態''' ({{en|state}}) という。
; 字母・記号・文字列
: 状態集合 {{mvar|Q}} と[[共通部分 (数学)|交わら]]ない有限集合 {{mvar|Γ}} を'''[[アルファベット (計算機科学)|字母]]'''（{{en|alphabet}}）といい、字母の元 {{math2|1=''a'' &isin; ''Γ''}} を'''記号''' ({{en|symbol}}) という。重複を許した有限個の記号の列全体からなる集合を {{math|''Γ''{{sup|*}}}} と表し、その元 {{math2|1=''x'' &isin; ''Γ''{{sup|*}}}} を字母 {{mvar|Γ}} の'''文字列'''（{{en|string}}）または'''文'''（{{en|statement}}）という。
; 空白記号
: 字母 {{mvar|Γ}} のある元を'''空白記号''' ({{en|blank}}) と定め、{{mvar|b}} で表す。
; 入力字母・入力記号
: 字母から空白文字を除いた {{math2|1=''Γ'' &minus; {{mset|b}}}} の部分集合 {{mvar|Σ}} を'''入力字母'''（{{en|input alphabet}}）といい、入力字母の元を'''入力記号'''（{{en|input symbol}}）という。
; 遷移函数
: [[写像]] {{math2|1=''δ'': ''Q'' &times; ''Γ'' → ''Q'' &times; ''Γ'' &times; {{mset|left, right}}}} を'''遷移函数'''という。{{math2|1=''δ''(''q'', ''a'') = (''q&prime;'', ''a&prime;'', ''m'')}} は、「現在の状態が {{mvar|q}} であり、着目位置の記号が {{mvar|a}} であれば、状態を {{mvar|q&prime;}} に移し、着目位置に記号 {{mvar|a&prime;}} を書き込んでから、着目位置を {{math2|1=''m'' &isin; {{mset|left, right}}}} 方向に1つずらす」と読む。
; 初期状態
: 状態集合 {{mvar|Q}} のある元 {{math|1=''q''<sub>init</sub>}} を'''初期状態'''（{{en|initial state}}）と定める。
; 受理状態
: 状態集合 {{mvar|Q}} のある元 {{math|1=''q''<sub>acc</sub>}} を'''受理状態'''（{{en|accepting state}}）と定める。
; 状況
: <math display="inline">\mathit\Gamma \cup Q</math> 上の（片側）無限列のうち、状態集合 {{mvar|Q}} の元がちょうど1度現れ、また空白 {{mvar|b}} 以外の記号が有限回しか現れないものをチューリングマシン {{mvar|M}} の'''状況'''（{{en|configuration}}）という。遷移函数 {{mvar|δ}} は、状況から状況への写像を自然に定める。
; 受理
: 「チューリングマシン {{mvar|M}} が入力文字列 <math display="inline">x \in \Sigma^*</math> を'''受理'''（{{en|accept}}）する」とは、チューリングマシン {{mvar|M}} が初期状態 {{math|''q''{{sub|init}}}} で入力文字列 {{mvar|x}} が与えられた状況 <math display="inline">q_\mathrm{init} x b b \cdots</math> に対し、遷移函数 {{mvar|δ}} を有限回作用させ受理状態 {{math|''q''{{sub|acc}}}} へ遷移した状況 <math display="inline">q _\mathrm{acc} b b \cdots</math> が得られることをいう。
; 実行時間・記憶領域量
: チューリングマシン {{mvar|M}} が入力文字列 {{math2|1=''x'' &isin; ''Σ''<sup>*</sup>}} を受理するまで遷移函数を作用させる最小の回数をチューリングマシン {{mvar|M}} の入力文字列 {{mvar|x}} に対する'''実行時間'''とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する'''記憶領域量'''という。

M が言語 <math>L \subseteq \mathit\Sigma^*</math> を'''認識'''するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は'''帰納可枚挙'''（{{en|recursively enumerable}}）あるいは'''計算可枚挙'''（{{en|computably enumerable}}）であるという。L と <math>\mathit\Sigma^* \setminus L</math> がともに帰納可枚挙であるとき、Lは'''帰納的'''（{{en|recursive}}）あるいは'''決定可能'''（{{en|decidable}}）であるという。

より精細に、自然数から自然数への写像 t に対し、M が L を'''時間計算量'''［ないし'''空間計算量'''］t で認識するとは、M が L を認識し、かつ各 <math>x \in L</math> に対する <math>M</math> の実行時間［ないし記憶領域量］が <math>t (\left| x \right|)</math> 以下であることをいう。ここで <math>\left| x \right|</math> は文字列 x の長さを表す。

== 変種 ==
=== 細かい相違 ===
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
* 字母<math>\mathit\Gamma</math>の大きさ（それが<math>\mathit\Sigma</math>を含む有限集合であるかぎり）。
* 遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
* 文字列を受理するさい、テープ上の記号をすべて<math>b</math>にする必要があるか、受理状態へ移るだけでよいか。
* テープが両方向に無限であるか、片側に終端があるか。
* さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
* テープの本数。
空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数<math>\delta</math>を<math>Q \times \mathit\Gamma ^2</math>から<math>Q \times \mathit\Gamma \times \{\mathrm{left}, \mathrm{right}\} ^2</math>への写像とし、状況の定義も適切に変更する。

=== 変換機 ===
言語を認識するだけでなく、<math>\mathit\Sigma ^*</math>から<math>\mathit\Sigma ^*</math>への部分函数<math>f</math>を'''計算'''する機械を考えることもできる。すなわち機械<math>M</math>は、各<math>x \in \mathrm{dom} (f)</math>に対しては文字列<math>f (x)</math>をテープに書いてから初めて受理状態へ移り、<math>x \notin \mathrm{dom} (f)</math>に対しては決して受理状態へ移らない。このような<math>M</math>が存在するとき、<math>f</math>は'''部分帰納的'''あるいは'''[[計算可能性理論|計算可能]]'''（computable）であるという。

=== 決定的と非決定的 ===
遷移関数<math>\delta</math>において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値（すなわちその時にすべき動作）が、高々一つならば、そのチューリングマシンは「決定的」（deterministic）である。これに対し、動作が複数の場合は「非決定的」（non-deterministic）であり、受理の意味も再定義して、[[非決定性チューリングマシン|非決定的チューリングマシン]]や乱択チューリングマシンが定義される。また、未来と過去を逆にしても決定的であるのが[[可逆チューリングマシン]]である。

=== 神託つき機械 ===
{{main|神託機械}}
質問状態を加える。

== 万能チューリングマシン ==
遷移規則をうまく構成することで、「いかなるチューリングマシンであろうとも、それを模倣することが可能なチューリングマシン（万能チューリングマシン）」が可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。（[[エミュレータ (コンピュータ)|エミュレータ]]の原理）

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist2}}

=== 出典 ===
{{Reflist}}

==関連項目==
{{commons|Category:Turing machines}}
* [[チューリング完全]]
* [[非決定性チューリングマシン]]
* [[コルモゴロフ複雑性]]
* [[ライフゲーム]]
* [[停止性問題]]
* [[可逆チューリングマシン]]
* [[オートマトン]]
* [[ラングトンのアリ]]

== 外部リンク ==
解説
* {{Wayback|url=http://www.scholarpedia.org/article/Turing_machine |title=Turing machine |date=20080212061156}} - [[スカラーペディア]]百科事典「チューリングマシン」の項目。
{{SEP|turing-machine/|Turing Machines}}
* {{MathWorld|urlname=TuringMachine|title=Turing Machine}}

その他
* [http://wired.jp/wv/2007/10/26/%e3%80%8c%e3%82%a6%e3%83%ab%e3%83%95%e3%83%a9%e3%83%a0%e6%b0%8f%e3%81%ae%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%e3%80%8d%e3%82%9220%e6%ad%b3%e3%81%ae%e5%ad%a6/ 「ウルフラム氏のチューリングマシン」を20歳の学生が証明]

{{Computer-stub}}
{{Normdaten}}
{{デフォルトソート:ちゆうりんくましん}}

[[Category:チューリングマシン|*]]
[[Category:抽象機械]]
[[Category:理論計算機科学]]
[[Category:計算モデル]]
[[Category:形式手法]]
[[Category:数学に関する記事]]
[[Category:アラン・チューリング]]
[[Category:数学のエポニム]]