The Rapidly-Accelerating Computer

From: Saibal Mitra <smitra.domain.name.hidden>
Date: Thu, 14 Sep 2000 17:58:16 +0200

 Question: Does the AUH exclude universes in which a RAC can be built? The following text explaining the RAC is from the website:

 http://www.ix.de/tp/english/inhalt/kolu/2414/1.html

``Just to see how extreme the Turing-Church Thesis actually is, a few years ago mathematician Ian Stewart half-jokingly suggested the idea of what he called, The Rapidly-Accelerating Computer (RAC). His goal was to show what it is exactly about computing machines that gives rise to things like the unsolvability of the Halting Problem and uncomputable numbers. Basically, the problem is the assumption that it takes a fixed, finite amount of time to carry out a single step in a computation. For his idealized computer, Turing assumed an infinite amount of memory. Stewart, on the other hand, considers the RAC, whose clock accelerates exponentially fast, with pulses separated by intervals of 1/2, 1/4, 1/8 ...seconds. So the RAC can cram an infinite number of computational steps into a single second. Such a machine would be a sight to behold as it would be totally indifferent to the algorithmic complexity of any problem presented to it. On the RAC, everything runs in bounded time.

The RAC can calculate the incalculable. For instance, it could easily solve the Halting Problem by running a computation in accelerated time and throwing a switch if and only if the program stops. Since the entire procedure could be carried out in no more than one second, we then only have to examine the switch to see if it's been thrown. The RAC could also prove or disprove famous mathematical puzzles like Goldbach's Conjecture (every even number greater than 2 is the sum of two primes). What's even more impressive, the machine could prove all possible theorems by running through every logically valid chain of deduction from the axioms of set theory. And if one believes in classical Newtonian mechanics, there's not even a theoretical obstacle in the path of actually building the RAC.

In Newton's world, we could model the RAC by a classical dynamical system involving a collection of interacting particles. One way to do this, suggested by Z. Xia and J. Gerver, is to have the inner workings of the machine carried out by ball bearings that speed up exponentially. Because classical mechanics posits no upper limit on the velocities of such point particles, it's possible to accelerate time in the equations of motion by simply reparameterizing it so that infinite subjective time passes within a finite amount of objective time. What we end up with is a system of classical dynamical equations that mimics the operations of the RAC. Thus, such a system can compute the uncomputable and decide the undecidable.

Of course, just like Turing's infinite-memory machine, the RAC is impossible in the real world. The problem is that at the nitty-gritty level of real material objects like logical gates and integrated circuits, there is a theoretical upper bound to the rate of information transfer (i.e., velocities). As Einstein showed, no material object can exceed the velocity of light. Thus, there is no RAC and, hence, no devices to complete the incompletable.

But the fact that we can never construct a RAC in no way precludes the possibility that some analogue device like a DNA computer or a quantum machine cannot be made that will allow us to transcend the Turing limit, and, hence, compute the uncomputable.

Saibal
Received on Thu Sep 14 2000 - 09:12:46 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST