Timeline for Turing Machine which generates order on the set of its states
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17 at 13:50 | history | edited | Jukka Kohonen | CC BY-SA 4.0 |
tag fix (order lattices) & clarify confusing sentence & slight formatting improvements
|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Mar 10, 2017 at 9:42 | history | edited | CommunityBot |
replaced http://24.media.tumblr.com/ with https://24.media.tumblr.com/
|
|
| Mar 8, 2011 at 17:58 | history | edited | kakaz | CC BY-SA 2.5 |
added 462 characters in body
|
| 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 | answer | added | Joel David Hamkins | timeline score: 3 | |
| Mar 8, 2011 at 13:53 | comment | added | kakaz | @Joel David Hamkins - Thank You a lot! So in general it suggest that this class of machines is equivalent to TM without loops. If You think it is worth to write Your comment as answer I will accept it. | |
| Mar 8, 2011 at 13:44 | history | edited | kakaz | CC BY-SA 2.5 |
added 4 characters in body
|
| Mar 8, 2011 at 13:34 | comment | added | Joel David Hamkins | Kakaz, if the transition induces a partial order, then the machine cannot find itself in the same local configuration again after leaving it, since a partial order has no loops. It follows that the length of the whole computation is bounded by $|Q\times L|$, and so by running the computation for that long, you can solve the halting problem. Thus, these machines are very weak in computational power. | |
| Mar 8, 2011 at 13:34 | history | edited | kakaz | CC BY-SA 2.5 |
added 8 characters in body; added 4 characters in body; added 14 characters in body
|
| Mar 8, 2011 at 12:53 | comment | added | kakaz | @Joel David Hamkins - I am just curious if such class of TM is interesting. And I would be glad to see any reference on it. It is just free idea... "And the halting problem for such machines will be decidable" - is is about machines with (II) property or for more general machines set for which T(q,a) generates lattice (or possibly other algebraic) structure? | |
| Mar 8, 2011 at 12:32 | history | edited | kakaz | CC BY-SA 2.5 |
added 6 characters in body
|
| Mar 8, 2011 at 11:57 | comment | added | Joel David Hamkins | What kind of answer are you seeking? Such a TM cannot be universal, for example, since computation must stop very quickly. And the halting problem for such machines will be decidable, and even polytime decidable, for the same reason. | |
| Mar 8, 2011 at 11:43 | history | edited | kakaz | CC BY-SA 2.5 |
added 927 characters in body
|
| Mar 8, 2011 at 9:21 | comment | added | supercooldave | Cross posted on CSTheory stackexchange: cstheory.stackexchange.com/questions/5346/… | |
| Mar 8, 2011 at 8:24 | history | asked | kakaz | CC BY-SA 2.5 |