> It arguably isn't possible to understand the halting problem without some notion of encoding (of the data that constitute a Turing machine in a form that can

> It arguably isn't possible to understand the halting problem without some notion of encoding (of the data that constitute a Turing machine in a form that can itself be processed by a Turing machine) You can understand the halting problem without math. You can explain it logically. But the halting problem has nothing to do with Turing. As I stated, the halting problem was invented/discovered by someone else years after Turing's death. We don't need Turing or the Turing machine to understand undecidability since Alonzo Church already proved undecidability before Turing. > but there's no reason that encoding has to be number-theoretic Sure. Turing encoded to the standard description ( letters ) and to description numbers. But number theory is necessary if you want to follow Turing's approach since you need to show for starters that turing machines and computable numbers are enumerable.