Puaun, Andrei, and Cezar Campeanu. “Computing Beyond the Turing Limit Using the H Systems”. DNA Computing, Springer, 2005, pp. 24-34, https://doi.org/10.1007/11493785_3.

Genre

  • Book, Section
Contributors
Author: Puaun, Andrei
Author: Campeanu, Cezar
Date Issued
2005
Publisher
Springer
Place Published
Berlin
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.

Language

  • English
Page range
24-34
Host Title
DNA computing
Series Title
Lecture Notes in Computer Science; 3384