Re: The Rapidly-Accelerating Computer

From: Marchal <marchal.domain.name.hidden>
Date: Wed Oct 18 06:56:15 2000

Hal Finney wrote:

>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.

Only with oracle machine.

>That in itself implies, in a sense, an infinite amount
>of time or effort to initialize the TM.

As Wei Dai says that would be equivalent to the UTM with an oracle for the
halting problem. (at least with the right symbol on the tape).
Note that there are still unsolvable problems for such an UTM.
There is an infinite lattice of degrees of unsolvability.
A transfinite alpha-machine with alpha stritly bigger than omega could
do much more than an omega machine.

>Why would we hesitate to accept
>the infinite stream of 1's but not the infinite stream of 0's?

Because the zero are supposed to be there by default. To put the "ones"
you
need omega times.


Wei Dai wrote:

>I'll point out that this model
>actually makes it clear that normal observer + RAC is not equivalent to
>CSO + normal computer.

A CSO + a never stopping computer can emulate the halting problem in the
sense
that he can guess that a non-stopping program will never stop ... until
he changes
his mind (after seeing a program which halts). In this way
he will always be wrong, but he will be less and less wrong with time. In
the limit
he will be correct. It is ambiguous if the limit can be said to exist in
our case. (There is a "well know" theorem in Recursion theory explaining
this: the
Schoenfield modulus lemma).

Bruno
Received on Wed Oct 18 2000 - 06:56:15 PDT