Timeline for Rationale behind an requirement on Turing machines
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2014 at 8:04 | comment | added | Hans-Peter Stricker | Notice further, that $b$ can not only be read but also be written. | |
| Sep 29, 2014 at 7:49 | comment | added | Hans-Peter Stricker | Re-reading your answer I am still not satisfied: In Hopcroft/Ullman's definition of a Turing machine as a 7-tupel the blank symbol $b$ is distinguished (among the tape symbols), but there seems to be no requirement on a Turing machine involving $b$. Especially the transition function $\delta$ can be defined on the whole tape alphabet (including $b$). The same holds - by the way - for the initial state $q_0$. | |
| Aug 26, 2014 at 21:07 | comment | added | Joel David Hamkins | Of course one can still expect to compute some things, as you've indicated. But your machines are not suitable for a full-fledged theory of computability, since they are not Turing complete. We could also handicap other kinds of Turing machines in various ways, to prevent them from being Turing complete, such as by insisting they run in polynomial time. Such a polytime handicap offers a computational model of an extremely robust and important class of decidability problems. Your model similarly handles some class of decidability problems, but I'm not sure how robust it is. | |
| Aug 26, 2014 at 20:58 | comment | added | Hans-Peter Stricker | Yet another question: Does your answer imply that my $T_{bin-double}$ computes nothing, thus is no Turing machine at all? And what about $T_{id}$ which rewrites the first symbol and halts? $T_{id}$ seems to work equally well for unary and binary and arbitrary $k$-ary (interpreted) inputs. | |
| Aug 26, 2014 at 20:14 | comment | added | Hans-Peter Stricker | Yes, this is what I mean. But you put the head initially on a specific square (left or equal to the first $1$). | |
| Aug 26, 2014 at 20:12 | comment | added | Joel David Hamkins | I understood the situation as: you write the input on the tape (in binary) and then fill up the rest of the tape with blanks, that is, with $0$s. | |
| Aug 26, 2014 at 20:10 | comment | added | Hans-Peter Stricker | One question: you write "input is padded with infinitely many additional $0$s". How can this be, when we have only finitely many $1$s? | |
| Aug 26, 2014 at 20:07 | comment | added | Joel David Hamkins | It is fine for MO, in my opinion. | |
| Aug 26, 2014 at 20:02 | comment | added | Hans-Peter Stricker | @Joel: Thank you very much! (Now, that I know and understand your answer, I see that my question was not really "research level". Do you find it inappropriate for MO, too?) | |
| Aug 26, 2014 at 20:01 | comment | added | Sridhar Ramesh | Heh, good point. Though we might also consider more sophisticated prefix-free encodings, the simplest is to reserve an "Ok, we're done" character, and that's basically the role the blank symbol plays. | |
| Aug 26, 2014 at 19:57 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 1 character in body
|
| Aug 26, 2014 at 19:56 | vote | accept | Hans-Peter Stricker | ||
| Aug 26, 2014 at 19:55 | comment | added | Joel David Hamkins | Yes. For example, one could use unary input, which amounts in this case to imposing the Hopcroft/Ulman requirement. | |
| Aug 26, 2014 at 19:53 | comment | added | Sridhar Ramesh | One might note that the proposed machine is Turing-complete using any computable prefix-free encoding of the natural numbers. | |
| Aug 26, 2014 at 19:44 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |