2
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If its operation is suitably arithmetized in well-known ways, why wouldn't my TM work outside the model in the meta-theory as well? $\endgroup$ – Russell Easterly Mar 20 '16 at 0:31
  • $\begingroup$ @RussellEasterly: Because (a) its input is a tape that has as many ones on it as the meaning of the numbers it is supposed to add, not the names those numbers have when we look at them from the outside. For non-standard elements such an input tape doesn't even exist in the meta-theory. $\endgroup$ – Henning Makholm Mar 20 '16 at 0:37
  • 1
    $\begingroup$ This might be easier to visualize if you constructed an explicit example out of the ordinal numbers (e.g. $0, 1, 2, \dots, \omega, \omega + 1, \omega + 2, \dots$). $\endgroup$ – Kevin Mar 20 '16 at 1:25
  • 5
    $\begingroup$ Another way to describe the situation is that, when this TM works inside the model and adds two nonstandard numbers, it will use a nonstandard amount of time (and a nonstandard amount of space). Such infinitely long "computations" are not what we (on the outside) view as genuine computations. $\endgroup$ – Andreas Blass Mar 20 '16 at 1:29
1
$\begingroup$

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.

$\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.