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

From: <hal.domain.name.hidden>

Date: Tue, 17 Oct 2000 09:06:44 -0700

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

Date: Tue, 17 Oct 2000 09:06:44 -0700

Wei writes:

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

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