Hypercomputation


A major theme of the 20th Century has been the growing understanding of the nature of computation. This began in earnest in the 1930's with the independent introduction of several theoretical models of computation, including the recursive functions, the lambda calculus and the Turing machine. While these models were very different in character, they were soon proven to be of equal power and are now widely considered to represent the most powerful level of computation possible. Turing machines, in particular, have been a very influential model and are the basis for the physical computers we use today.

There has been much study of models of computation that have the same power as the Turing machine and also considerable study of weaker models. Hypercomputation is the relatively unexplored field in which models of computation with more power than the Turing machine are studied. Such models have historically been considered implausible because it is difficult to see how we could physically construct a machine more powerful than the Turing machine. However, there are now models of hypercomputation which take their inspiration from physical theories including General Relativity, Quantum Mechanics and even Newtonian Mechanics.

Our physical theories tell us about many limits imposed by the laws of physics. For example, Special Relativity tells us that the speed of light is an upper limit to the speeds at which matter can travel. Is there corresponding limit to the computations that can be performed within the universe? If so, what is it? And do our different theories give us different answers? These are very important questions and we can hardly just assume that the limit is Turing computation. Whichever way these questions are answered, we would learn something deep and important about the nature of the universe.

The possibility of hypercomputation also has many interesting and important philosophical implications. For example, there are physical theories in which we could build machines capable of proving all the truths of arithmetic and physical theories in which we could not. We do not know which category our universe falls into. Gödel's Incompleteness Theorem tells us that no Turing machine can prove all the truths of arithmetic and this is often taken to mean that some of these truths will be forever out of our reach (or that we could never know the answer without using our insight). However, we can now see that whether or not we can find all truths of arithmetic is an inherently empirical matter: it depends upon the nature of our universe, and cannot be determined a priori.


Hypercomputation: computing more than the Turing machine
  In 2002, I started my work on hypercomputation with this, my Honours thesis. In it, I survey much of the field and link together the rather scattered results. I compare the proposed hypermachines in terms of their power and their required resources, then demonstrate several important implications that hypercomputation bears for mathematics, physics, computer science and philosophy. If you are at all interested, please have a look. I've tried my hardest to present hypercomputation in a manner that is both useful for active researchers in the field and accessible to the casual (but interested) reader.

Using biased coins as oracles
  In 2003–4, I spent a lot of time researching hypercomputation with Prof. Tien Kieu of Swinburne University. This paper was one of the results of that collaboration. We demonstrate how one could perform oracular hypercomputation without requiring arbitrarily precise physical measurement. Instead, our method involves measuring the bias of a coin through a (long) sequence of tosses. By avoiding arbitrarily precise measurement, our technique shows how oracular computation could be compatible with the Heisenberg Uncertainty Principle.

The diagonal method and hypercomputation
  This paper (from 2004) is another result of the collaboration with Tien. Some recent papers had claimed not only that hypercomputation is physically impossible, but that it is logically impossible. This was based upon a misunderstanding of the use of the diagonal method to show that no Turing machine can compute the halting function. In this paper we expose that misunderstanding and give a nice characterisation of exactly what the diagonal method does and does not show.

The many forms of hypercomputation
  In late 2004 I was asked to write an introduction to hypercomputation for a special issue of the Journal of Applied Mathematics and Computation. In it, I characterise the many models of hypercomputation that have been presented and assess their plausibility.

How to simulate everything (all at once)
  I show that we can simulate a preposterous amount of things using a regular Turing machine, including uncountably many hypercomputational universes.