3
$\begingroup$

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.

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

Presumably what you describe as Peano's axioms for addition has been studied as Presburger arithmetic, which is known to be consistent and complete (therefore decidable). This seems to disallow the "embedding" of a universal Turing machine in that theory since then the halting problem would be decidable.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.