4 ms·
To your point, Turing's paper 'On Computable Numbers' doesn't even mention the length of the tape. He doesn't specify that it must be infinite at all.
by leroy-is-here 3y ago
To your point, Turing's paper 'On Computable Numbers' doesn't even mention the length of the tape. He doesn't specify that it must be infinite at all.
- schoen 3y agoI'm surprised to see that, but all subsequent authors have required it to be infinite (as a condition to distinguish it from other models of computation), and Turing himself later referred to it as infinite: https://en.wikipedia.org/wiki/Turing_machine#Physical_description https://en.wikipedia.org/wiki/Turing_machine#Physical_descri...
- eesmith 3y agoWhile the paper does not explicitly state it, he shows that π and e are computable. Those cannot be expressed on a fixed-length tape. There is also a demonstration why an infinite number of symbols does not give more computability over a finite number of symbols. I believe this only makes sense if the tape length is infinite.
- leroy-is-here 3y agoYeah, the model only makes sense with an infinite length tape. I only mention it because many commenters get stuck on the word 'infinite' without realizing how inconsequential it is.