Unfortunately, a major problem stems from a lack of understanding of many common terms today. Turing completeness does not require an infinite tape, and it was not an infinite tape that Turing mentioned in his paper; it was an unbounded system. Importantly, you cannot have a Turing machine with an infinite tape rather than an unbounded tape—by definition. An infinite tape is not related to a problem that can be computed. When both Church and Turing wrote their papers, the computer they discussed was human. The individual who was the mathematician doing the problems was termed a computer. So when we are talking about ... (full story)