HypercomputationA 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
Using biased coins as oracles
The diagonal method and hypercomputation
The many forms of hypercomputation
How to simulate everything (all at once)
|