Timeline for Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2020 at 5:05 | comment | added | Yuval Filmus | The pointers are implemented on the tape. You’ll notice when they cross. Unfortunately I cannot provide the full details, since I need to leave something for you to do. | |
| May 7, 2020 at 23:43 | comment | added | Jesus is Lord | Agreed. How does one "know" when the pointers meet? Is that part of the state transition? If the pointer is encoded as a space, are you saying the pointers are moving O(n) space along the input tape? | |
| May 7, 2020 at 21:28 | history | answered | Yuval Filmus | CC BY-SA 4.0 |