POSITION-DETERMINISTIC MACHINE AND METHODS FOR NONDETERMINISTIC COMPUTING

摘要

In the disclosed position-deterministic machine (PDM) and its simulation methods, a user problem to be solved is represented as a special kind of nondeterministic Turing machine, called PDM, with an input X to it. Deterministic methods of using deterministic components and recursive relations for the simulation of a PDA on an input X are disclosed. The disclosed methods decrease deterministic computational time complexity from 2^T(n) currently to nT(n) in the present invention for a PDM of nondeterministic computational time complexity T(n) on an input X of length n.