(by Gemini)
The Set-Theoretic Nucleus of Non-Determinism
The distinction between deterministic and non-deterministic Turing machines (DTMs and NTMs) is foundational to computational theory. From the perspective of computability, the models are equivalent—they recognize precisely the same class of languages. From the perspective of computational complexity, however, their relationship remains the most profound open question in the field.
The chasm between $\mathbf{P}$ and $\mathbf{NP}$ does not arise from a radical restructuring of the machine model. Instead, it emerges from a single, subtle modification in the formal, set-theoretic definition of the machine itself.
The Shared Formal Structure
At their core, both DTMs and NTMs are defined using the same foundational structure: a 7-tuple specifying the finite sets of states, input symbols, and tape symbols, along with the initial state, blank symbol, and the set of final (or accepting) states.
The fundamental divergence—the conceptual break from which all of complexity theory blossoms—lies entirely within the definition of the fifth component: the transition function.
The Crux: A Difference in Codomain
The essence of determinism versus non-determinism is captured by the codomain of the transition function.
-
For a Deterministic Turing Machine (DTM):
The transition function is a map whose domain is the Cartesian product of the set of non-final states and the set of tape symbols. Its codomain is a single element from the Cartesian product of the state set, the tape alphabet, and the set of possible head movements (left or right). For any given non-final state and tape symbol, the machine's next configuration is uniquely determined.
-
For a Non-deterministic Turing Machine (NTM):
The transition function's domain is identical: the Cartesian product of non-final states and tape symbols. The critical difference is its codomain. The function does not map to a single outcome-tuple; it maps to the power set of the set of all possible outcome-tuples. In other words, for any given configuration, the transition function returns a set of possible next configurations.
Consequence 1: The Shape of Computation
This formal distinction in the transition function directly dictates the "shape" of the computation itself.
A DTM's computation is a linear sequence of configurations. Given an initial configuration, the transition function defines at most one successor, resulting in a single computational path.
An NTM's computation is a tree. The initial configuration is the root. Each time the transition function returns a set with more than one element, the computation branches. The entire computation is the set of all possible paths originating from the root.
Consequence 2: The Definition of Acceptance
This structural divergence (sequence vs. tree) fundamentally alters the condition for accepting an input.
DTM Acceptance: A DTM accepts an input if its singular computation path enters a configuration whose state is a member of the set of final states.
NTM Acceptance: An NTM accepts an input if there exists at least one path in its computation tree that terminates in a configuration whose state is a member of the set of final states.
This existential nature is the formal embodiment of non-determinism. The machine "accepts" if any valid path succeeds, regardless of how many other paths may fail, reject, or loop indefinitely. This single set-theoretic shift—from an element to a power set—is the formal mechanism that separates $\mathbf{P}$ from $\mathbf{NP}$.
===
非決定性の集合論的な核
決定性チューリングマシン（DTM）と非決定性チューリングマシン（NTM）の区別は、計算理論の根幹をなすものです。計算可能性理論の観点では、両モデルは等価であり、まさに同じ言語クラスを認識します。しかし、計算複雑性理論の観点では、その関係性はこの分野における最も深遠な未解決問題として残っています。
$\mathbf{P}$ と $\mathbf{NP}$ の間の深淵は、マシンモデルの根本的な再構築から生じるのではありません。そうではなく、マシン自体の形式的、集合論的な定義における、たった一つの、そして微妙な変更から生じるのです。
共通の形式的構造
その核において、DTMとNTMはともに同一の基本構造を用いて定義されます。それは、状態の有限集合、入力記号の有限集合、テープ記号の有限集合、さらには初期状態、空白記号、そして最終（または受理）状態の集合を指定する7つ組です。
根本的な相違、すなわち全ての計算複雑性理論がそこから花開くことになる概念的な分岐点は、完全に第5の構成要素、すなわち遷移関数の定義の中に存在します。
核心：終域の違い
決定性と非決定性の本質は、遷移関数の**終域（Codomain）**によって捉えられます。
-
決定性チューリングマシン（DTM）の場合:
遷移関数は写像であり、その定義域は非最終状態の集合とテープ記号の集合の直積です。その終域は、状態の集合、テープ記号の集合、そして可能なヘッドの移動（左または右）の集合の直積から取られる単一の要素です。いかなる非最終状態とテープ記号が与えられても、マシンの次の様相（configuration）は一意に決定されます。
-
非決定性チューリングマシン（NTM）の場合:
遷移関数の定義域は（DTMと）同一です。すなわち、非最終状態の集合とテープ記号の集合の直積です。決定的な違いはその終域にあります。この関数は単一の結果の組に写像されるのではなく、すべての可能な結果の組の集合のべき集合（Power Set）に写像されます。言い換えれば、いかなる様相が与えられても、遷移関数は可能な次の様相の集合を返すのです。
帰結1：計算の形状
この遷移関数における形式的な区別が、計算自体の「形状」を直接的に決定します。
DTMの計算は、様相の線形な**系列（Sequence）**です。初期様相が与えられると、遷移関数は高々1つの後続状態を定義するため、結果として単一の計算経路が生まれます。
NTMの計算は、**木（Tree）**です。初期様相が根（Root）となります。遷移関数が複数の要素を持つ集合を返すたびに、計算は分岐します。計算全体とは、根から派生するすべての可能な経路の集合となります。
帰結2：受理の定義
この構造的な相違（系列 対 木）は、入力を受理するための条件を根本から変えてしまいます。
DTMの受理: DTMは、その単一の計算経路が、状態として最終状態の集合の要素を持つ様相に至った場合に、その入力を受理します。
NTMの受理: NTMは、その計算木の中に、状態として最終状態の集合の要素を持つ様相で終了する経路が少なくとも1つ存在する場合に、その入力を受理します。
この「存在的」な性質こそが、非決定性の形式的な具現化です。すなわち、他のどれだけ多くの経路が失敗し、拒否し、あるいは無限ループに陥ろうとも、有効な経路が1つでも成功すればマシンは「受理」するのです。この、単一の要素からべき集合へ、というたった一つの集合論的な移行こそが、$\mathbf{P}$ と $\mathbf{NP}$ を分かつ形式的なメカニズムなのです。