Maybe my question doesn't make sense, because I lack some more thorough understanding, but I was curious if arithmetic was Turing complete?

As I understand it, a "model of computation" is a mechanism where you can compute outputs from inputs. Thus a "computation" is just a mapping from inputs to outputs.

So if say the universe of possible inputs and outputs is: 1 and 2. This would be all possible computations:

1 -> 1
1 -> 2
1 -> 1,2
1 -> 2,1
2 -> 1
2 -> 2
2 -> 1,2
2 -> 2,1
1,2 -> 1
1,2 -> 2
1,2 -> 1,2
1,2 -> 2,1
2,1 -> 1
2,1 -> 2
2,1 -> 1,2
2,1 -> 2,1

Now, I think this isn't even technically the full set, because the full set would be infinite, since I could have repeated inputs and outputs like 1,1 -> 2,2,1,1. But at least this is the general gist which I understand.

And in my "model of computation", I should be able to say, apply the computation X to some inputs, where X is one of the above mapping, and get back the corresponding outputs.

So from this, I understand that the Turing Model is proven to be able to map all inputs to outputs over the universe of non complex numbers.

So my question is, would arithmetic be Turing Complete in its ability to map inputs to outputs? Or is there some mappings that can not be formulated using arithmetic, but can using the Turing model?


It depends what you mean by "arithmetic".

It's a fairly well-known result that Peano arithmetic (PA) is powerful enough to model Turing machines.

There are other models of arithmetic, such as Presburger arithmetic (which is strictly weaker; it's essentially PA without multiplication) and real closed fields with a partial order, which are known to be decidable.

| cite | improve this answer | |
  • $\begingroup$ Hum, I guess this is where my understanding fails me. The "arithmetic" I'm thinking of is the one I was thought in high-school :p $\endgroup$ – Didier A. Feb 14 '19 at 2:49
  • $\begingroup$ Peano arithmetic is equivalent to what you learned in elementary school: addition, subtraction, multiplication of integers. $\endgroup$ – Wandering Logic Feb 15 '19 at 15:27
  • 1
    $\begingroup$ Similarly, real closed fields are real numbers with addition, subtraction, multiplication, division, and "less than" comparison. It's interesting that "arithmetic" with essentially the same set of operations is undecidable on integers but decidable on real numbers. (If this seems strange, consider that integer linear programming is much harder than rational integer programming.) $\endgroup$ – Pseudonym Mar 19 '19 at 22:30

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.