Ejemplos de máquinas de turing biológicas [cerrado]

Se han construido varias máquinas de Turing utilizando computación de ADN. Una de estas máquinas se ha utilizado para resolver el problema de satisfacibilidad booleana, otra se ha utilizado para resolver el problema de correspondencia de postes acotados, ambos problemas combinatorios NP-difíciles de resolver para las computadoras convencionales. Además, se construyó una computadora de ADN que juega la estrategia óptima en tic-tac-toe .

Las computadoras de ADN almacenan información en secuencias de ADN y realizan cálculos mediante la comparación de bases de ADN y otras estrategias de biología molecular. En principio, el ADN almacena información mucho más densa que cualquier disco duro moderno y utiliza órdenes de magnitud menos energía por cálculo que una computadora convencional ($10^{-22}$contra$10^{-10} \frac{J}{operation}$) sin embargo, hasta ahora la E/S es lenta y los cálculos son comparativamente propensos a errores, lo que limita el uso práctico de la computación de ADN.

Además, un artículo reciente ha demostrado que los motores moleculares pueden realizar sumas básicas y resolver el problema de la suma de subconjuntos NP-completos mediante la exploración de redes fabricadas nanolitográficamente. Esto también podría, en principio, usarse para construir una máquina de Turing.