- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Wei Dai <weidai.domain.name.hidden>

Date: Tue, 17 Oct 2000 10:07:48 -0700

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

Date: Tue, 17 Oct 2000 10:07:48 -0700

On Tue, Oct 17, 2000 at 09:06:44AM -0700, hal.domain.name.hidden wrote:

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.

I think the infinite tape is just a notational convenience. You could

define the TM as having a finite tape that grows as needed.

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

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