0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\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
  • 2
    $\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
0
$\begingroup$

PA represents the same relations that TMs accept.

The Arithmetic you learned in elementary school forms the individual functions and expressions of a programming language. For example, you can assign variable A the value of 1+1 e.g. $A=1+1; in the PHP programming language. Arithmetic tells us that A now equals 2.

However, a Turing Complete (every) Programming Language also provides commands to execute a series of statements in an order that depends on the values of variables. We can say: if $A>1 $B=$A+1; This means that is variable A has a value greater than 1 then variable B will be given the value of 1 more than A.

By using these control commands in conjunction with assignment commands, we can calculate functions far beyond addition, subtraction, multiplication and divisions. We can generate prime numbers, for example.

With the addition of control commands, we have a Turing Complete programming language. We also have the possibility of a program going in circles forever - until we manually stop it. Alan Turing proved in 1937 (13 years before electronic computers were invented) that we can't always tell if a given program will end up going in circles forever.

I am sure you never got into an infinite loop performing Arithmetic assignments in school. But you also probably didn't generate prime numbers either.

So that is the trade-off. Just Arithmetic alone calculates simple things, like the cost of supper. But if you want to delve into more complex matters that involve Arithmetic functions, you'll have to use a complete Programming Language - and you'd better be careful.

A computer is like a powerful car. It can take you to the beach in a few minutes, but it can also take you off a cliff.

Drive safely!

$\endgroup$
0

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.