Re: The Rapidly-Accelerating Computer

From: Wei Dai <weidai.domain.name.hidden>
Date: Tue, 17 Oct 2000 02:59:39 -0700

On Fri, Oct 13, 2000 at 08:25:39PM -0700, hal.domain.name.hidden wrote:
> I'm not sure it would be zero. The program for the CSO is not
> particularly complex compared to other observer programs. If you have the
> program for a constant-speed observer then you only need to simulate the
> program, inserting ever increasing delays between simulated clock cycles.
>
> Now all you have to do is wait infinity+1 ticks of the UTM and you will
> have your CSO at subjective time 1, and the program to create him was
> not particularly long or unlikely.

Did you really have in mind something like the following?

for (i=0; i<infinity+1; i++)
        ComputeNextStepOfUniverse();
OutputObserverMoment();

I'm not sure how you can define a model of computation that involves
transfinite time (i.e., one where the above program would have a
well-defined output). If it is possible, I have a feeling that the model
might be equivalent to an UTM that has access to an oracle for the
halting problem.

> This sounds correct; it's hard to imagine a problem which takes an
> infinite amount of computation to solve, but whose solutions could be
> tested in finite time. Is this a theorem of computational theory?

If the solutions can be tested in finite time, then you can solve the
problem by testing all possible solutions, and this process would halt in
a finite amount of time. (I'm assuming that "no solution" counts as a
solution.)

> On the other hand there might be theoretical reasons to believe in the
> RAC; for example, if the laws of physics appear to be such as to allow
> for infinitely fast computation, then it might be that we believe in
> the RAC due to our understanding of the details of its construction.
> It's like our belief today in the correctness of large proofs that can
> only be verified by computer.

It boils down to how to define the measure of observer moments. If you
define it with a standard UTM, then nothing can convince you that RACs
exist. If the laws of physics appear to allow infinitely fast
computation, you'll just assume that you don't have a complete
understanding of those laws.
Received on Tue Oct 17 2000 - 03:04:40 PDT