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
