Unambiguous Turing machine¶
A nondeterministic Turing machine with at most one accepting computation path on each input, regardless of how many rejecting branches it has.
Core Idea¶
An unambiguous Turing machine is nondeterministic but places a strict cap on successful computations: for every input, at most one complete branch accepts. Other branches may reject or fail to halt according to the recognition setting. The property concerns accepting path count, not the number of possible transitions, final outputs, or total branches. A deterministic machine is automatically unambiguous because it never has two alternative accepting histories.
Without a time restriction, unambiguous machines can recognize the recursively enumerable languages; the condition does not make them inherently efficient. UP uses polynomial-time unambiguous decision, as the MIT complexity notes confirm. Unambiguity alone does not imply polynomial time, and a particular ambiguous machine does not show that its language lies outside UP, because a different unambiguous decider might exist. The universal per-input quantifier matters: one input with two accepting paths is enough to disqualify that machine.
Scope of Application¶
These uses count accepting paths for every input under a declared machine and resource model.
- Computability theory. Classify accepting-path uniqueness separately from recognizability.
- Complexity classes. State a polynomial bound before invoking UP.
- Algorithm audit. Find inputs with duplicate accepting witnesses that violate a proposed machine's unambiguity.
- Model comparison. Distinguish deterministic, unambiguous and unrestricted nondeterministic computation.
Clarity¶
For each input, count accepting computation branches, not all branches. Inclusion: One accepting and several rejecting paths is unambiguous. Exclusion: Two accepting paths on one input violate the property. Nearest boundary: A deterministic machine is an included special case, while UP adds polynomial-time decision; uniqueness alone does not imply efficiency.
Manages Complexity¶
Acceptance-path counting compresses a potentially huge computation tree into one defining test. It retains the crucial distinction between the machine's branching structure, its language, and the resource-bounded class used to decide that language.
Abstract Reasoning¶
- Fix an input and its initial configuration.
- Examine all nondeterministic successor histories that could accept.
- Test whether zero or one, never two, accept for every input.
- Keep rejecting branches outside the uniqueness count.
- Add time/space and halting assumptions before making complexity-class conclusions.
Knowledge Transfer¶
The unique-successful-run idea transfers to other nondeterministic models only after their acceptance semantics are specified. A proof for one input does not transfer to all inputs, and the polynomial-time UP conclusion does not transfer to an unrestricted recognizer.
Relationships to Other Abstractions¶
Current abstraction Unambiguous Turing machine Domain-specific
Parents (1) — more general patterns this builds on
-
Unambiguous Turing machine is a kind of Nondeterministic Turing machine Domain-specific
An unambiguous Turing machine retains nondeterministic transition and acceptance semantics while allowing at most one accepting path per input.
Hierarchy paths (2) — routes to 2 parentless roots
- Unambiguous Turing machine → Nondeterministic Turing machine → Branching and Merging → State and State Transition → Phase Space
- Unambiguous Turing machine → Nondeterministic Turing machine → Branching and Merging → Versioning
Neighborhood in Abstraction Space¶
Unambiguous Turing machine sits in a moderately populated region (55th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Queueing, Networks & Concurrent Systems (9 abstractions)
Nearest neighbors
- NEXPTIME — 0.87
- Decision Tree Model — 0.86
- Exact Quantum Polynomial Time — 0.85
- Prim’s Algorithm — 0.85
- Angelic Nondeterminism — 0.85
Computed from structural-signature embeddings · 2026-10-08