Timeline for Turing Machine which generates order on the set of its states
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 8, 2011 at 17:38 | comment | added | kakaz | Although I agree that "machine cannot find itself in the same local configuration again" it is worth to note hat there stil may be loop in the state space of machine. Example of such machine You may find in Hopcroft, Ullman "Introduction to Automata T., Languages and Computation". on page 175 in Polish edition there is an example of simple machine for which there is relation T(q_i,a_k) = (q_j,a_s) and k<= s. Even so machine perform loop in its internal states. So the class of such machines may be still not trivial but of course they are bounded as You wrote. See above. | |
| Mar 8, 2011 at 17:31 | vote | accept | kakaz | ||
| Mar 8, 2011 at 14:18 | vote | accept | kakaz | ||
| Mar 8, 2011 at 17:31 | |||||
| Mar 8, 2011 at 14:10 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |