Timeline for What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 5, 2014 at 23:14 | comment | added | Carl Mummert | @Joel: Yes, exactly. Some other models have a different, unchangeable tape symbol to mark the left edge of the tape. | |
| May 5, 2014 at 23:10 | comment | added | Joel David Hamkins | @CarlMummert Oh, I agree that there are a variety of TM models. In some of the semi-infinite models, one can check the left-most cell condition, if they operate according to the rule that moving left from that cell simply causes no movement (but the program continues anyway). In this model, one can institute a left-cell check, by means of writing some string (e.g. 10), and then moving left and then checking if it is still there in the expected place. If not, you're on the left-most cell. But in other models, moving left from the left-most cell causes computation to stop. | |
| May 5, 2014 at 23:09 | comment | added | Emil Jeřábek | It’s clear from the first example in the question that they meant numbers to be written in binary. | |
| May 5, 2014 at 22:55 | comment | added | Carl Mummert | @Joel: By the way, there is a technical reason to start the machine on the first input symbol, which is to accommodate machines that have a one-sided (i.e. semi-infinite) input tape, which are common in the computational complexity literature. These need to know where the left end of the tape is, because in the usual framework they have no way to find it otherwise. | |
| May 5, 2014 at 22:20 | history | edited | Carl Mummert | CC BY-SA 3.0 |
added 512 characters in body
|
| May 5, 2014 at 22:13 | comment | added | Carl Mummert | @Joel: Silly Turing machines - everyone has their own idea how they work! In my mind they need to start on the first symbol of input. This is also (likely) why the author said that $h(x) = x-1$ takes $O(|x|)$ steps; it would also take only one step if the machine started on the last digit. I'll edit the answer, however. | |
| May 5, 2014 at 22:10 | comment | added | Joel David Hamkins | I think there are reasonable TM models where $x\mapsto x+1$ is computable in constant time. For example, if we use unary notation on a bi-infinite tape, with the convention that the head sits on the end of the input string, then all we have to do is add one more $1$ and halt, which takes constant time. | |
| May 5, 2014 at 18:23 | history | answered | Carl Mummert | CC BY-SA 3.0 |