Timeline for Halting of transfinite Turing Machine question
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 1, 2017 at 3:10 | comment | added | Joel David Hamkins | As for the operation of transfinite Turing machines, Gerhard, probably my article linked in my answer could serve as a gentle introduction. Later work generalized this to tapes of length Ord, as in the question, but it is easier to start with the normal hardware. I think we were both in Berkeley at the time when the ITTM theory was first getting started, in the early 1990s. Do you remember Jeff Kidder and I sharing an office? And Andy Lewis was also there, but didn't get involved until later. | |
| Aug 1, 2017 at 3:02 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 741 characters in body
|
| Aug 1, 2017 at 2:59 | comment | added | Joel David Hamkins | Well, I assumed that $p$ is a Turing machine program, which does have a simple description in how it is to operate. If that is not what is meant, then one would have to specify the computational model more fully. But the argument I gave is actually quite general, and will still apply to other models, provided that the operation of the machine can be described in set theory and is absolute to those models of set theory. It would be very strange for a model of computability to not be absoluten, since it would mean the operation of the machine would depend on the universe in which it is run. | |
| Aug 1, 2017 at 2:55 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 741 characters in body
|
| Aug 1, 2017 at 2:55 | comment | added | Gerhard Paseman | Doesn't this argument depend on a certain "simplicity" in the description of p? Is it not possible that p is complex enough that L of p contains enough ordinals to render L-S and condensation ineffective in shortening the running time? I am hoping you can make this argument even more explicit to me , who has almost no experience with transfinite Turing machines. (In particular, can I understand p like a machine with a transfinite oracle?) Gerhard "Amazon Sells No Transfinite Raspberry-Pis" Paseman, 2017.07.31. | |
| Aug 1, 2017 at 2:43 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |