Computing beyond the Turing limit using the H systems
|Section title||Computing beyond the Turing limit using the H systems|
|Section author(s)||Cezar Campeanu, Andrei Puaun|
|Book title||DNA computing|
|Abstract||We introduce a new variant of the heavily studied model of H systems. The new variant will use an external factor to determine the set of the active splicing rules. We improve the best known universality result for time-varying H systems with respect to the diameter of such a system and we prove that if the function recording the behavior of the external factor is uncomputable so is the newly defined model, thus exceeding the Turing barrier. We also construct an universal system that is also more powerful than the Turing Machines.|
Using APA 6th Edition citation style.
Times viewed: 423