Deterministic methods

Shapiro et al implemented finite-state machines in DNA:
Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, and E. Shapiro. Programmable and autonomous computing machine made of biomolecules. Nature 414 (2001) 430-434

Finite-state machines are the bottom of the of the computing-power hierarchy.

Next come pushdown automata; these can be simulated by DNA hairpins.

At the top of the hierarchy are Turing machines, cellular automata, and ordinary computers.

Cellular automata have been simulated by Seeman et al.

prev  next