On Tue, Oct 17, 2000 at 09:06:44AM -0700, hal.domain.name.hidden wrote:
> 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.
I think the model he presents IS equivalent to the
UTM-with-halting-problem-oracle model. I'll point out that this model
actually makes it clear that normal observer + RAC is not equivalent to
CSO + normal computer. The former program would look like this:
infinity {ComputeNextStepOfRAC();}
ComputeNextStepOfObserver();
OutputObserverMoment();
The latter progrm would look like this:
infinity {ComputeNextStepOfUniverse();}
OutputObserverMoment();
Basicly to get the desired observer moment you need to run a step of the
observer after the infinite loop, which you can't do in the CSO case.
> 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.
I think the infinite tape is just a notational convenience. You could
define the TM as having a finite tape that grows as needed.
> 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.
Well, no. As I said earlier it's possible to define the measure on
observer moments using alternative models of computation that are not
finite and discrete. The UTM model seems natural but I don't really know
how to justify it.
Received on Tue Oct 17 2000 - 10:14:46 PDT