Are there any examples of biological Turing machines? And what can they do?
4
-
2$\begingroup$ Take a look at: quora.com/Is-DNA-a-Turing-machine or nature.com/nrg/journal/v13/n7/full/nrg3197.html. $\endgroup$– AlexDeLargeCommented Jun 18, 2016 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 AlbaughCommented Jun 18, 2016 at 15:55
-
$\begingroup$ Are you asking for "natural" Turing machines or artificially created ones? $\endgroup$– fileunderwaterCommented Jun 18, 2016 at 17:26
-
$\begingroup$ Hm interesting question. I think natural Turing machines would be way more interesting. But both are interesting. $\endgroup$– JonnyPythonCommented Jun 18, 2016 at 20:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ Thx, that's about artificial ones. What about Turing machines in nature? $\endgroup$ Commented Jun 19, 2016 at 11:49
-
1$\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$– ThawnCommented Jun 19, 2016 at 12:06
-