3 ms·
Memory growth is not a consideration in the academic proof, Turing machine tape is infinite in both directions.
by jmpe 13y ago
Memory growth is not a consideration in the academic proof, Turing machine tape is infinite in both directions.
- taejo 13y agoTuring 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]