Abstract:
We deal here with the computational capacity of DNA when
splicing it, by means of restriction enzymes and ligases. We introduce a
new distributed structure of a computing system (we call it two-level H
system), with each component working by splicing (according to internal
splicing rules) and communicating, also by splicing, according to external
splicing rules. This architecture is proven to be computationally universal,
systems with three components characterize the recursively enumerable
languages. The possibility of designing universal DNA computers based
on splicing is inferred on this basis.