alt Hacker NewsThe context acting as a "theoretically limitless tape" while simultaneously the step being O(1) are contradictory. You cannot have it both.
Replies
anon291 • today at 6:26 AM
It's not contradictory at all. The dfa at each step of the turing machine model is also o(1).
➕ show 1 reply
The context can change each time. To implement a UTM only requires 2 states and 3 symbols or the reverse.
So if you use the context not as a tape in itself, but as an io channel to read/write an infinite tape, the context for any given step can remain fixed in size, and so the step itself can be O(1).