4 ms·
right. the tape only has to be $steps long, for $steps steps of computation, because that's the longest distance the head can travel at all. any program that
by cracki 17y ago
right.
the tape only has to be $steps long, for $steps steps of computation, because that's the longest distance the head can travel at all.
any program that eventually halts, has a finite number of steps, so the band can be finite.
the only thing that requires an infinite band, is a non-halting program. and non-halting programs (unlike real-world servers and OSes) don't have a result as defined by the turing machine concept.
- argv_empty 17y agothe only thing that requires an infinite band, is a non-halting program. Sure, that's the only type of program that would use the whole tape, but given any tape of finite length, there's a (program, input) pair that needs a longer tape.