Are there any examples of biological Turing machines? And what can they do?

  • 2
    $\begingroup$ Take a look at: quora.com/Is-DNA-a-Turing-machine or nature.com/nrg/journal/v13/n7/full/nrg3197.html. $\endgroup$ – AlexDeLarge Jun 18 '16 at 15:51
  • 2
    $\begingroup$ Welcome to BiologySE and thanks for your question! It always helps by adding references and some background information so that others can understand what you're asking - and it will strengthen your question. $\endgroup$ – Vance L Albaugh Jun 18 '16 at 15:55
  • $\begingroup$ Are you asking for "natural" Turing machines or artificially created ones? $\endgroup$ – fileunderwater Jun 18 '16 at 17:26
  • $\begingroup$ Hm interesting question. I think natural Turing machines would be way more interesting. But both are interesting. $\endgroup$ – JonnyPython Jun 18 '16 at 20:20

There have been several Turing machines constructed using DNA computing. One of these machines has been used to solve the boolean satisfiability problem, another was used to solve the bounded post correspondence problem, both NP-hard combinatorial problems which are difficult for conventional computers to solve. Also, a DNA computer was constructed that plays the optimal strategy in tic-tac-toe.

DNA computers store information in DNA sequences and perform calculations by DNA baseparing and other molecular biology strategies. In principle, DNA stores Information much denser than any modern hard drive and uses orders of magnitude less energy per calculation than a conventional computer ($10^{-22}$ vs $10^{-10} \frac{J}{operation}$) however, so far i/o is slow and calculations are comparatively error prone, limiting the practical use of DNA computing.

Also, a recent article has demonstrated that molecular motors can perform basic addition and solve the NP-complete subset sum problem by exploring nanolithographically fabricated networks. This could also, in principle, be used to construct a turing machine.

| improve this answer | |
  • $\begingroup$ Thx, that's about artificial ones. What about Turing machines in nature? $\endgroup$ – JonnyPython Jun 19 '16 at 11:49
  • $\begingroup$ Well, the brain most likely fulfills the criteria for a turing machine on some level. Also, there is this very nice answer to the question "is DNA a turing machine" on quora. That details how protein biosynthesis could be viewed as (almost) a turing machine. Finally, transposons fulfil many of the criteria of a turing machine. However, none of these examples are turing complete, except maybe for the brain but there it is not well understood how. $\endgroup$ – Thawn Jun 19 '16 at 12:06
  • $\begingroup$ Thx very interesting. $\endgroup$ – JonnyPython Jun 19 '16 at 12:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.