For the most important class of problem in computer science,non-deterministic polynomial complete problems, non-deterministic UTMs (NUTMs)are theoretically exponentially faster than both classical UTMs and quantummechanical UTMs (QUTMs).
This design is based on Thue string rewriting systems,and thereby avoids the limitations of most previous DNA computing schemes: allthe computation is local (simple edits to strings) so there is no need forcommunication, and there is no need to order operations. The design exploitsDNA’s ability to replicate to execute an exponential number of computationalpaths in P time. Each Thue rewriting step is embodied in a DNA edit implementedusing a novel combination of polymerase chain reactions and site-directedmutagenesis. We demonstrate that the design works using both computationalmodeling and in vitro molecularbiology experimentation: the design is thermodynamically favorable,microprogramming can be used to encode arbitrary Thue rules, all classes ofThue rule can be implemented and non-deterministic rule implementation. In anNUTM, the resource limitation is space, which contrasts with classical UTMs andQUTMs where it is time. This fundamental difference enables an NUTM to tradespace for time, which is significant for both theoretical computer science andphysics. It is also of practical importance, for to quote Richard Feynman’there’s plenty of room at the bottom’.
This means that a desktop DNA NUTMcould potentially utilize more processors than all the electronic computers inthe world combined, and thereby outperform the world’s current fastestsupercomputer, while consuming a tiny fraction of its energy. However, we acknowledge that further experimentation isrequired to complete the physical construction of a fully working NUTM. Indeed,we are unaware of any fully working molecular implementation of a UTM, far lessan NUTM. The key point about implementing a UTM compared with special purposehardware is that special purpose hardware typically needs to be redesigned foreach new problem. By contrast, in a UTM only the software needs to be changedfor a new problem, and the hardware stays fixed. The situation for molecularUTMs is currently similar to that of QUTMs where hardware prototypes haveexecuted significant computation, but no full physical implementation of a QUTMexists. The greatest challenge in developing a working NUTM iscontrol of ‘noise’.
Noise was a serious problem in the early days of electroniccomputers however; the problem has now essentially been solved. Noise is alsothe most serious hindrance to the physical implementation of QUTMs, and mayactually make QUTMs physically impossible. By contrast, in an NUTM, well-understoodclassical approaches can be employed to deal with noise.
Best services for writing your paper according to Trustpilot
These classicalmethods enable unreliable components to be combined together to form extremelyreliable overall systems.The way in NUTM for noise reduction is that the use oferror-correcting codes. These codes are used ubiquitously in electronic computers,and are also essential for QUTMs. Classical error-correcting code methods canbe directly ported to NUTMs. Another way is therepetition of computations. The most basic way to reduce noise isto repeat computations, either spatially or temporally.
The use of a polynomialnumber of repetitions does not affect the fundamental speed advantage of NUTMsover classical UTMs or QUTMs.Mosteffort on non-standard computation has focused on developing QUTMs. Steadyprogress is being made in theory and implementation, but no QUTM currentlyexists. Although abstract QUTMs have not been proven to outperform classicalUTMs, they are thought to be faster for certain problems. The best evidence forthis is Shor’s integer factoring algorithm, which is exponentially faster thanthe current best classical algorithm. While integer factoring is in NP, it isnot thought to be NP complete, and it is generally believed that the class ofproblems solvable in P time by a QUTM (BQP) is not a superset of NP.NUTMsand QUTMs both utilize exponential parallelism, but their advantages anddisadvantages seem distinct. NUTMs utilize general parallelism, but this takesup physical space.
In a QUTM, the parallelism is restricted, but does notoccupy physical space (at least in our Universe). In principle therefore, itwould seem to be possible to engineer an NUTM capable of utilizing anexponential number of QCs in P time.Advocates of the many-worlds interpretation of quantummechanics argue that QUTMs work through exploitation of the hypothesizedparallel universes. Intriguingly, if the multiverse were an NUTM this wouldexplain the profligacy of worlds.
In an NUTM, the resource limitation is space,which contrasts with classical UTMs and QUTMs where it is time. Thisfundamental difference enables an NUTM to trade space for time, which issignificant for both theoretical computer science and physics.NUTM m 1: n relation possible h but QUTM m 1:1 hta hNUTMs are much faster than QUTMs in terms of speeds
