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:

We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete problems in polynomial time). We discover that all these claims rely on the provision of one or more unphysical resources.

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ⁿ units of time to perform the n^th step of a program then it will have completed a countable infinity of steps in one time unit. With such a machine the halting problem is no problem.

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:

There are various models that use General Relativistic effects to allow the computer to experience a different (and infinite) proper time from the (finite) time that the observer experiences. The best known of these is the Malament–Hogarth spacetime model (Etesi and N´emeti; 2002; Hogarth; 1992). The underlying concept is that the computer is thrown into one of these spacetimes, where it can be observed externally. If a computation does not halt, this can be determined in a finite time by the observer in the external reference frame, and so the set-up solves the Halting Problem. 

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:

We have provided an overview of certain claims of hypercomputation and super-Turing computation in a range of unconventional computing devices. Our overview covers many specific proposals, but is not comprehensive. Nevertheless, a common theme emerges: all the devices seem to rely on one or another unphysical property to work: infinite times or speeds, or infinite precision, or uncomputable advice, or some unconsidered exponential physical resource. 

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:

1st Law of Computing: You cannot solve uncomputable or N P-hard problems efficiently unless you have a physical infinity or an efficient oracle.

2nd Law of Computing: There are no physical infinities or efficient oracles.

3rd Law of Computing: Nature is physical and does not solve uncomputable or N P-hard problems efficiently.

Corollary: Nature necessarily solves uncomputable or N P-hard problems only approximately.

So far so reasonable, but wait:

This raises the question: what can UCOMP do? Given that UCOMP does not solve uncomputable or even N P-hard problems (and this also applies to quantum computing), what is the future for UCOMP?

Notice the extension of three laws of computing to apply to quantum computing as well as classical!

More Information

Computability and Complexity of Unconventional Computing Devices by Hajo Broersma, Susan Stepney, and Goran Wendin

Related Articles

Quantum Physics Is Undecidable

The Facts Of Quantum Life 

Halting Problem Used To Prove A Robot Cannot Computably Kill A Human 

The Machine In The Ghost       

What Is Computable?       

Solve The Riemann Hypothesis With A Quantum Computer       

The Programmer's Guide to Chaos       

What Is Computable?       

What is a Turing Machine?       

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

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info