# Can we construct a universal Turing machine using only Peano's axioms for addition?

Can we construct a universal Turing machine (UTM) using only Peano's axioms for addition?

We know that arithmetic without addition is complete, and that adding multiplication makes it incomplete.

I am trying to understand more deeply if there is a link between incompleteness and the existence of a UTM.

It has been shown by Chaitin that a UTM can exists as a Diophantine equation involving multiplication, addition and exponential. So a UTM from full arithmetic is definitely possible. No claims however are made as to if this is the logically simplest or not.

Furthermore, a UTM moves tapes left and right, write a symbol, erase a symbol, or read a symbol. These does not seem to be multiplicative operations.

• The piano's axioms? I prefer drums. Properly the name is Peano. – Oscar Lanzi Jul 2 '17 at 2:12
• @Oscar Autocorrect... – Alexandre H. Tremblay Jul 2 '17 at 2:15
• Hate that thing. I have had to make embarrassing edits to many answers when I spotted autocorrects. – Oscar Lanzi Jul 2 '17 at 2:16
• But autocorrect can be misled by such cues as extra "the"s. – Robert Soupe Jul 2 '17 at 2:16

You can encode any TM and its non-blank tape content (assuming we started with a finite part of the tape non-blank at the stat) using recursive functions, and every recursive function is representable using the language of arithmetic. Thus, using the Peano Axioms you can prove for any $n$ what the state (internal state and tape configuration (which includes osirion of head along tape)) is that the TM is in after $n$ steps of operation. So that is indeed how you could construct a kind of UTM: a UTM that proves using the Peano Axioms, together with a logic statement describing the initial state and input of a TM, what things look like every step of the way.