1

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?

Eduard
  • 304
  • It is obvious that one of the statements must be true. I do not understand the point of this question. – Peter Aug 02 '22 at 07:54
  • The assertion "p halts on n" is an expression that could be written with just arithmetic operators like + 0, successor, exists, for all etc...? – Eduard Aug 02 '22 at 07:59
  • Or in other words why this two statement must be the output of a theorem-enumeration machine that only writes true arithmetical statements? It will output "I like potatoes" or "I don't like potatoes"? – Eduard Aug 02 '22 at 08:03
  • It is like showing that any Turing machine can be expressed as a number, when setting some coding mechanism? Related to the existence of an universal Turing machine? To halt or not is an arithmetical property? – Eduard Aug 02 '22 at 08:14
  • 1
    @Eduard this seems like a good discussion! But one perhaps best asked on a more conversation-based platform like a forum. I.e; I worry this may be closed do to lack of a concrete question, or matters that concern personal opinion. – Graviton Aug 02 '22 at 09:05

2 Answers2

2

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.

Noah Schweber
  • 245,398
1

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

Peter Smith
  • 54,743