2 ms·
Turing machines have may have infinite memory, but they can also only write one step per cell. So a polynomial-time TM can't use superpolynomial memory.
by taejo 13y ago
Turing machines have may have infinite memory, but they can also only write one step per cell. So a polynomial-time TM can't use superpolynomial memory.
- deleted 13y ago[deleted]