No Super Turing Machines |

Written by Mike James | |||

Wednesday, 15 February 2017 | |||

Every now and again you will read of a breakthrough claiming that some weird computer or other can solve NP problems in P. Putting this another way, we are presented with a super Turing machine capable of computing something that is non-computable. It usually turns out to be more complicated than the headlines suggest.
A new paper casts some light on what constitutes a super Turing machine and why they are simply non-physical.This is one of the most interesting papers I have read in a while.
Most of us know that there are things that a Turing machine cannot compute and it seems to have something to do with the distinction between a true infinity and unbounded but finite. What this paper considers is exponentially increasing resources and how this increases the range of computation. This is so because arranged correctly such UCOMP Unconventional Computing devices can reach an infinite use in a finite time. This is something a Turing machine cannot do and as a result there are things that a UCOMP can compute that a Turing machine cannot. The researchers say:
What these machines seem to have in common is that they find a way to realize infinity. For example, if you have a computer that takes 1/2 The interesting aspect of this paper is that it gives examples and discusses a range of machines that go beyond Turing, the general relativistic machine for example:
This probably appeals to the physicist, but the mathematician probably prefers the real number machine which is essentially any computational process that works with exact real numbers. This leads to all sorts of errors in thinking. Recently a memresistor machine was claimed to solve NP problems in P, but it only did if you could make measurements to infinite accuracy - which is of course not possible. The same is true of many traditional "computations". Take straightedge and compass construction. These are capable of computing an exact representation of, say, the square root of two but of course there is nothing exact about it unless the line you draw is infinitely narrow.t Read the rest of the paper. There is a lot about quantum computation, DNA computing, evolutionary processors, optical computing, mem computing and, most surprisingly, brain computing. Before you get carried away it is worth stating part of the conclusion:
At the end of the paper the authors propose three laws of computation. They do so "slightly tongue-in-cheek" but I think they are probably correct:
So far so reasonable, but wait:
Notice the extension of three laws of computing to apply to quantum computing as well as classical!
## More InformationComputability and Complexity of Unconventional Computing Devices by Hajo Broersma, Susan Stepney, and Goran Wendin ## Related ArticlesQuantum Physics Is Undecidable Halting Problem Used To Prove A Robot Cannot Computably Kill A Human Solve The Riemann Hypothesis With A Quantum Computer The Programmer's Guide to Chaos
To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |
|||

Last Updated ( Wednesday, 15 February 2017 ) |