Timeline for Is there any space(n) complete language?
Current License: CC BY-SA 2.5
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2010 at 19:22 | comment | added | Kristoffer Arnsfelt Hansen | I should also clarify to address the worries expressed in the previous answer of possible large alphabets and number of tapes of the Turing machine M in the language $L$ defined above. I shall simply only allow Turing machines M over a fixed tape alphabet and with a single work-tape. This ensures that $L$ is in $LINSPACE$. Also, by tape reduction and encoding alphabets, any $O(n)$ space bounded Turing machine can be converted into this form and still be $O(n)$ space bounded. | |
| Sep 27, 2010 at 19:09 | history | answered | Kristoffer Arnsfelt Hansen | CC BY-SA 2.5 |