As a proof of "There is no computable enumerable list of axioms that prove all and only the true statements of elementary mathematics", just run the theorem-enumeration machine with inputs p and n (p a turing-machine program and n its input) and wait for the assertion "p halts on n" or "p does not halts on n". Is it trivial that the statement "p halts on n" or "p does not halts on n" is expressible using elementary mathematics?
2026-04-07 09:38:22.1775554702
On
"P halts on n" as an elementary math statement
71 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
To find out more about the ideas behind Noah's answer, you might like to take a look at the chapter on “Halting and Incompleteness” in my An Introduction to Gödel‘s Theorems (originally CUP).
The book is in print as a pbk, but I've made the PDF of the 2nd edition free to download from https://www.logicmatters.net/igt
It's not trivial, in my opinion, but it is true. The arithmetical expressibility of Turing machine behavior is arguably implicit in Godel's proof of his first incompleteness theorem (despite Turing machines not yet having been introduced), but it finds its cleanest expression in Kleene's $T$-predicate.