Campeanu, C., & Puaun, A. (2005). Computing beyond the Turing limit using the H systems. In DNA computing (pp. 24-34). Berlin: Springer. doi:10.1007/11493785_3

Details

Title

Computing beyond the Turing limit using the H systems

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 Show moreWe 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. Show less