How can addition be non-recursive?

Question

Tennenbaum's theorem says neither addition nor multiplication can be recursive in a non-standard model of arithmetic. I assume recursive means computable and computable means computable by a Turing machine (TM).

The 3-state TM described below takes the unary representation of two natural numbers as input and outputs the unary representation of the sum of the two numbers. A unary representation is a string of 1's (possibly empty) followed by a 0. Given the input 110110 this TM will output 111100.

A0:1RB A1:1RA

B0:0LC B1:1RB

C0:0Halt C1:0Halt

This TM halts on any input tape with two 0's. It can add any two standard natural numbers in a finite number of steps. It must also work inside any non-standard model. Assume it didn't. Then we could define the set of numbers, $x$, such that this TM correctly adds $x+x$. Assuming this set has no largest element, it would be an inductive set since it includes all standard natural numbers. A non-standard model can't have an inductive proper subset proving this TM must work in any non-standard model.

Another scenario is when we have a non-standard model in a meta-theory like ZFC. We must assume our meta-theory uses a standard model of arithmetic. The TM above still adds standard natural numbers, but Tennenbaum's theorem says there can't be an algorithm in the meta-theory that computes addition in this non-standard model.

Why can't the TM I describe above compute addition in this non-standard model? Is it simply because the input tape would have to be infinitely long if one of the input numbers is an "infinite" number?

Answer 1

Tennenbaum's theorem doesn't claim that your TM doesn't work inside the model (if its operation is suitably arithmetized in well-known ways).

It says that there cannot exists a TM that works outside the model and tells us onlookers what the model thinks the sum of two of its elements are.

More precisely, suppose we have a countable non-standard model of PA. Without loss of generality we can take this to be $(\mathbb N,0,f,g,h)$ where $\mathbb N$ is our naturals, $f:\mathbb N\to\mathbb N$ is some function that is the model's successor function and $g,h:\mathbb N\times\mathbb N\to\mathbb N$ are its addition and multiplication operations. We know that somehow this structure satisfies all of the axioms of PA.

We're also assuming that $(\mathbb N,0,f,g,h)$ is not isomorphic as a structure to the usual $(\mathbb N,0,{+1},{+},\times)$.

Tennenbaums theorem now says that if all these assumptions hold, $g$ and $h$ cannot be computable functions. On the other hand $f$ can be computable, but that doesn't help us much.

Suppose we want to use your method (and the recursion equations) to compute $g(a,b)$, which is the model's idea of the sum of the elements represented by $a$ and $b$. We can start at $0$ and increase it (using the computable $f$ function) repeatedly until we reach $b$ -- and for each time we increase it we also increase $a$. The $a$ we end up with must be $g(a,b)$.

The reason this doesn't work is that if $b$ is a non-standard element, we never actually reach $b$ when we search through $0, f(0), f(f(0)), f(f(f(0)))$ and so forth, working outside the models. This only gives us the standard elements of the model, and knowing $f$ does not in itself determine how addition of non-standard elements work.

Answer 2

If you take a countable nonstandard model, you first enumerate that model in $\omega$. That is, you consider the domain of the model to be a set $\{ a_0, a_1, \ldots \}$.

In your algorithm, the input $n$ represents the actual number $n$, and not the element $a_n$ of the model. But this is not what the question is asking, it's asking if there is an algorithm that, given input $\langle n, m \rangle$, outputs a number $k$ such that $a_n + a_m = a_k$. Tenenbaum's theorem says that there is no such algorithm.