2 ms·
Turing-completeness requires the ability to recall an infinite number of bits, which is obviously impossible in physical reality. A Turing machine with that pro
by fluoridation 3y ago
Turing-completeness requires the ability to recall an infinite number of bits, which is obviously impossible in physical reality. A Turing machine with that property removed is a pushdown automaton.
- garganzol 3y ago> Turing-completeness requires the ability to recall an infinite number of bits It does not. The number of available bits just determines the maximum complexity of the system that can be built.
- fluoridation 3y agoI mean, the tape being infinite is part of the definition of what a Turing machine is.