Timeline for Is every recursive language recognized by a mortal Turing machine?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 15, 2014 at 20:27 | comment | added | domotorp | Yes, the difference is that I supposed that every tape content is finite and we know where the boundaries are. Otherwise mortal TM's are just constant, as you write. | |
| Feb 15, 2014 at 20:16 | comment | added | Joshua Grochow | @MarzioDeBiasi: The notion of mortal considered in that paper requires a machine halt in a finite number of steps even if it is started with an infinite amount of arbitrary data on its tape. But I think domotorp's construction at most works for finite configurations. For example, in a configuration with an infinite-length input, domotorp's M gets caught in an infinite sequence of copying the infinite-length input to the separate memory tape... | |
| Feb 15, 2014 at 19:38 | comment | added | Marzio De Biasi | while writing my answer, I read yours ... which say the opposite :-) ... perhaps I'm wrongly interpreting what is a string accepted by a mortal Turing machine ? | |
| Feb 15, 2014 at 19:28 | history | answered | domotorp | CC BY-SA 3.0 |