Nondeterministic Turing Machine Equivalent to Deterministic Turing Machine

This article needs to be tidied. In particular: substandard Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

Nondeterministic Turing Machines and Deterministic Turing Machines are Equivalent

Every Deterministic Turing Machine can be run by a Nondeterministic Turing Machine

The machine definitions only differ in whether $(q′,Y′,d)\in\delta(q,Y)$ or $(q′,Y′,d)=\delta(q,Y)$. Define singletons $\delta(q,Y)=\{(q',Y',d)\}$ from the deterministic mapping and run your DTM on your NTM.

Every Nondeterministic Turing Machine can be run by a Deterministic Turing Machine

Albeit slow: sequentialize the parallel search breadth-first. Define yourself a Universal Turing Machine that can single-step an instantaneous description of your NTM and follow a given NTM transition table like this: 1. for each applicable transition, copy the instantaneous description to the end of the tape and perform its step. 2. when the transition table is exhausted, mark the original instantaneous description processed and attend to the next as in 1. unless you halt for simulating an accepting state or having run out of unprocessed configurations.