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

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

Date: Wed Oct 18 06:56:15 2000

Hal Finney wrote:

Only with oracle machine.

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.

Because the zero are supposed to be there by default. To put the "ones"

you

need omega times.

Wei Dai wrote:

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

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