Wei writes:
> 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.
I found an amusing web page with a proposed programming language for
the RAC,
http://www.chiark.greenend.org.uk/~sgtatham/infinity.html.
Here is the program to decide Goldbach's conjecture:
true = 1;
infinity {
int i, j;
for (i = 2;; i += 2) {
for (j = i-1; j > 0; j--)
if (prime(j) && prime(i-j))
break;
if (j <= 0) /* this even number is NOT the sum of 2 primes */
true = 0;
}
}
printf("Goldbach's conjecture is %s\n", true ? "TRUE" : "FALSE");
This is presented as just an amusing speculation and perhaps can't
be made rigorous.
It's not clear to me what is wrong with letting a standard TM operate for
a transfinite number of steps. We usually give the TM an infinite tape,
and we feel free to imagine the infinite tape initialized with an infinite
number of symbols. That in itself implies, in a sense, an infinite amount
of time or effort to initialize the TM.
Can't we imagine discovering such a TM in operation, with its tape in
a state that could only be reached after an infinite number of steps?
Suppose the tape starts all 0's and the TM simply writes a 1 and steps
to the right. We find the machine in a state with an infinite number of
1's on the left and an infinite number of 0's on the right. This would
imply that it had been running forever. Why would we hesitate to accept
the infinite stream of 1's but not the infinite stream of 0's?
Having an oracle for the halting problem would let you answer any boolean
computational problem. From that you could get any numeric value to any
specified degree of precision. To actually have an infinitely precise
real number would require an infinitely large or detailed computer, which
may raise problems of its own.
Would you say that the an all-universe model automatically implies that
space is finite and discrete? It seems that if there are problems having
an infinite amount of time in the past, there might be analogous problems
to having an infinite amount of space to the left.
Hal
Received on Tue Oct 17 2000 - 09:18:55 PDT