Seong-lae ChoNTM
Let r = maxq,X |δ(q,X)|. So N has at most r possible choices in each step. Possible runs of N can be organized as a tree.
IDi1i2···in = The instantaneous description of N if it choses to take choice i1 in step 1, choice i2 in step 2, and so on.
Note that the r choices after each step are not the same! At each step, there are at most r choices
Definition
Equivalent definitions
- Verifiable in a polynomial time in DTM
- Solvable in a polynomial time in NTM
Mean
NTM requires not only dynamic memory tapes count but also dynamic computing processors. Modern computer approximate this but there are limited count. or processor and memory. Quantum Computer is how to implement NTM efficiently.
Quantum computing does allow for a kind of parallelism (through superposition), but it is constrained by quantum mechanics and is not equivalent to the unlimited parallelism of an NDTM. Furthermore, when a quantum computation is complete, the act of measuring the qubits to read out the result collapses their quantum state, limiting the information that can be extracted to a single outcome. This is fundamentally different from an NDTM, which, by definition, can "choose" the correct answer from among many possible computational paths.