非決定性チューリングマシン

理論計算機科学において、非決定性チューリングマシン( NTM ) は、特定の状況で複数の可能なアクションを指定する制御ルールを備えた計算の理論モデルです。つまり、決定性チューリングマシンとは異なり、NTM の次の状態は、そのアクションと現在見ているシンボルによって完全には決定されません。

NTM は、コンピュータの能力と限界を調べるための思考実験で使用されることがあります。理論計算機科学における最も重要な未解決問題の 1 つは、 P 対 NP 問題です。これは (他の同等の定式化の中でも)、非決定論的計算を決定論的コンピュータでシミュレートすることがどの程度難しいかという問題に関するものです。

本質的には、チューリング マシンは、一連のルールに厳密に従って、エンドレス テープ上で 1 つずつシンボルを読み書きする単純なコンピューターであると考えられています。チューリング マシンは、内部状態と現在表示されているシンボルに応じて、次に実行するアクションを決定します。チューリング マシンのルールの 1 つの例は、「状態 2 で 'A' が表示された場合は、それを 'B' に変更し、左に移動して状態 3 に切り替える」などです。

決定論的チューリング マシン(DTM)では、一連のルールによって、特定の状況に対して実行されるアクションが最大で 1 つ規定されます。

決定論的チューリング マシンには、テープ ヘッドの下の特定の状態とシンボルに対して次の 3 つのことを指定する 遷移関数があります。

• テープに書き込むシンボル（現在その位置にあるシンボルと同じになる場合もあれば、まったく書き込まない場合もあるため、実質的な変更はありません）
• 頭を動かす方向（左、右、どちらでもない）
• 有限制御のその後の状態。

たとえば、状態 3 のテープ上の X により、DTM はテープ上に Y を書き込み、ヘッドを 1 つ右に移動し、状態 5 に切り替わります。

決定論的チューリング マシンとは対照的に、非決定論的チューリング マシン( NTM ) では、一連のルールによって、特定の状況に対して実行されるアクションが複数規定される場合があります。たとえば、状態 3 のテープ上の X によって、NTM は次の操作を実行できます。

• Yを書いて右に移動し、状態5に切り替えます

または

• X を書いて左に移動し、状態 3 のままになります。

NTM は、これらのアクションのどれを実行するべきかをどのようにして「知る」のでしょうか。これには 2 つの見方があります。1 つは、マシンが「最も幸運な推測者」であると言うことです。マシンは、そのような遷移がある場合、最終的に受け入れ状態につながる遷移を常に選択します。もう 1 つは、マシンが多数のコピーに「分岐」し、それぞれが可能な遷移の 1 つに従うと想像することです。DTM には 1 つの「計算パス」がありますが、NTM には「計算ツリー」があります。ツリーの少なくとも 1 つのブランチが「受け入れ」条件で停止すると、NTM は入力を受け入れます。

非決定性チューリングマシンは、6つの要素から成る組として正式に定義できる。 ${\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}$

• ${\displaystyle Q}$有限の状態集合である
• ${\displaystyle \Sigma }$有限の記号集合（テープアルファベット）
• ${\displaystyle \iota \in Q}$初期状態
• ${\displaystyle \sqcup \in \Sigma }$空白の記号
• ${\displaystyle A\subseteq Q}$受け入れ（最終）状態の集合である
• ${\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)}$は遷移関係と呼ばれる状態と記号の関係です。は左への移動、は移動なし、 は右への移動です。${\displaystyle L}$${\displaystyle S}$${\displaystyle R}$

標準的な (決定論的)チューリング マシンとの違いは、決定論的チューリング マシンの場合、遷移関係は単なる関係ではなく関数であるということです。

構成と、テープの内容が与えられた場合のチューリング マシンの可能なアクションを記述する構成上のyields関係は、 yields関係が単一の値ではなくなったことを除いて、標準のチューリング マシンと同じです。(マシンが決定論的である場合、可能な計算はすべて単一の、場合によっては無限のパスのプレフィックスです。)

NTM の入力は、決定論的チューリング マシンと同じ方法で提供されます。マシンは、テープ ヘッドが文字列の最初の文字 (存在する場合) にある構成で起動され、それ以外の場合はテープはすべて空白になります。

NTM は、その文字列から始まる可能な計算パスの少なくとも 1 つがマシンを受け入れ状態にする場合にのみ、入力文字列を受け入れます。決定論的マシンで NTM の多数の分岐パスをシミュレートする場合、いずれかの分岐が受け入れ状態に達する とすぐに、シミュレーション全体を停止できます。

主に証明に使用される数学的構成として、NTM の定義にはさまざまな小さなバリエーションがありますが、これらのバリエーションはすべて同等の言語を受け入れます。

遷移関係の出力における頭の動きは、文字を使用する代わりに数値でエンコードされることが多く、頭の動きを左 (-1)、静止 (0)、右 (+1) で表します。これにより、遷移関数の出力が得られます。静止 (0) 出力を省略し、 ^[1]代わりに必要な静止遷移の推移閉包を挿入するの が一般的です。${\displaystyle \left(Q\times \Sigma \times \{-1,0,+1\}\right)}$

一部の著者は明示的な拒否状態を追加し、^[2] NTM が受け入れずに停止するようにします。この定義では、非決定的な分岐は受け入れることができるという非対称性が保持されますが、文字列を拒否するには すべての分岐を拒否する必要があります。

DTM で解決できる計算問題は NTM でも解決でき、その逆も同様です。ただし、一般に時間の複雑さは同じではないと考えられています。

NTM には特殊なケースとして DTM が含まれるため、DTM で実行できるすべての計算は、同等の NTM でも実行できます。

NTM は、同じ初期構成から生じる可能性のある計算のツリーを許可し、ツリー内のいずれかのブランチが文字列を受け入れる場合にその文字列を受け入れることができるため、DTM よりも強力であると思われるかもしれません。ただし、DTM を使用して NTM をシミュレートすることは可能であり、実際には複数の方法で実行できます。

1 つのアプローチは、構成が NTM の複数の構成を表す DTM を使用することです。DTM の操作は、各構成を順番に訪問し、訪問ごとに 1 つのステップを実行し、遷移関係が複数の継続を定義するたびに新しい構成を生成することから構成されます。

別の構成では、3テープDTMを使用してNTMをシミュレートします。最初のテープには常に元の入力文字列が保持され、2番目のテープはNTMの特定の計算をシミュレートするために使用され、3番目のテープはNTMの計算ツリー内のパスをエンコードします。^[3] 3テープDTMは、通常のシングルテープDTMで簡単にシミュレートできます。

2 番目の構成では、構築された DTM はNTM の計算ツリーの幅優先探索を効果的に実行し、受け入れ可能な計算が見つかるまで、長さが増加する順に NTM のすべての可能な計算を参照します。したがって、DTM の受け入れ可能な計算の長さは、一般に、NTM の最短の受け入れ可能な計算の長さの指数関数的になります。これは、DTM による NTM のシミュレーションの一般的な特性であると考えられています。コンピュータ サイエンスで最も有名な未解決の問題であるP = NP 問題は、この問題の 1 つのケース、つまり NTM が多項式時間で解決できるすべての問題が、必然的に DTM でも多項式時間で解決できるかどうかに関するものです。

NTM には、制限された非決定性という特性があります。つまり、NTM が常に特定の入力テープTで停止する場合、制限された数のステップで停止するため、可能な構成の数も制限されます。

量子コンピュータは、従来のビットではなく状態の重ね合わせが可能な量子ビットを使用するため、量子コンピュータはNTMであるという誤解が時々あります。^[4]しかし、専門家は（証明されていませんが）量子コンピュータのパワーは実際にはNTMのそれとは比較にならないと信じています。つまり、量子コンピュータではできない問題をNTMが効率的に解決できる可能性があり、その逆も同様です。^{[5] [より良い情報源が必要]}特に、NP完全問題はNTMでは多項式時間で解決できる可能性がありますが、量子コンピュータでは多項式時間で解決できない可能性があります。

直感的に言えば、量子コンピュータは、すべての可能な計算分岐が同時に実行されたことに対応する重ね合わせ状態になる可能性は確かにありますが (NTM と同様)、最終的な測定により、量子コンピュータはランダムに選択された分岐に縮小されます。この分岐は、指数関数的に多数の分岐の中から適切なソリューションを選択できる NTM とは異なり、一般に、求められているソリューションを表すものではありません。

• 確率的チューリングマシン

• Martin, John C. (1997)。「セクション 9.6: 非決定性チューリングマシン」。言語と計算理論入門(第 2 版)。McGraw-Hill。277 ～ 281 ページ。ISBN 978-0073191461。
• Papadimitriou, Christos (1993)。「セクション 2.7: 非決定性マシン」。計算複雑性(第 1 版)。Addison-Wesley。pp. 45–50。ISBN 978-0201530827。

• 非決定性マルチテープ チューリング マシンの C++ シミュレーター (フリー ソフトウェア)。
• 非決定性マルチテープ チューリング マシンの C++ シミュレーターのダウンロード リンク (sourceforge.net から)