Small Universal Bacteria and Plasmid Computing Systems

Bacterial computing is a known candidate in natural computing, the aim being to construct “bacterialcomputers”forsolvingcomplexproblems. Inthispaper,anewkindofbacterialcomputing system, named the bacteria and plasmid computing system (BP system), is proposed. We investigate the computational power of BP systems with finite numbers of bacteria and plasmids. Specifically, it is obtained in a constructive way that a BP system with 2 bacteria and 34 plasmids is Turing universal. The results provide a theoretical cornerstone to construct powerful bacterial computers and demonstrate a concept of paradigms using a “reasonable” number of bacteria and plasmids for such devices