Molecular implementation of simple logic programs

Autonomous programmable computing devices made of biomolecules could interact with a biological environment and be used in future biological and medical applications(1-7).. Biomolecular implementations of finite automata(8,9) and logic gates(4,10-13) have already been developed(14-18). Here, we report an autonomous programmable molecular system based on the manipulation of DNA strands that is capable of performing simple logical deductions. Using molecular representations of facts such as Man(Socrates) and rules such as Mortal(X) -> Man(X) (Every Man is Mortal), the system can answer molecular queries such as Mortal(Socrates)? (is Socrates Mortal?) and Mortal(X) (Who is Mortal?). This biomolecular computing system compares favourably with previous approaches in terms of expressive power, performance and precision(2,4,8,9,11,12,19). A compiler translates facts, rules and queries into their molecular representations and subsequently operates a robotic system that assembles the logical deductions and delivers the result. This prototype is the first simple programming language with a molecular-scale implementation.