A Non-Standard Post

Mike O'Donnell tells a story of talk he saw once where the speaker considered the following recursive program: f(n) := output 0 if n = 0; output f(n-1) otherwise. By straightforward induction one can show that for any natural number n, f(n) will halt in a finite number of steps. The speaker argued that if we take n to be a non-standard natural number (which is bigger than all the standard integers) than the program will never halt. Mike O'Donnell counters that it will halt, just in a non-standard number of steps.

Suppose we could prove P≠NP in the theory of arithmetic. I can create a machine M that solve SAT on standard formula φ using |φ|^k time if k is nonstandard: Since k and thus |φ|^k is greater than every standard integer, we have time to do exhaustive search. However there will be some nonstandard φ that M will fail to solve satisfiability in time |φ|^k time, for whatever the satisfiability question for nonstandard φ means.

Now suppose P=NP in the standard model but P≠NP in some non-standard model (and thus the P versus NP question is independent of the theory of arithmetic). We have a standard machine M and a standard integer k such that M(φ) correct computes whether a standard φ is in SAT in |φ|^k steps. But for some non-standard φ, M(&phi); would fail even though it gets to run in time n^k for the nonstandard n=|φ|. Even if we allow M and k to be non-standard there will be some φ that M will fail to determine satsifiability.

You can keep playing this game and never get into trouble assuming the theory of arithmetic is consistent. But I get a headache when I try to think what non-standard Turing maching, non-standard polynomial running time and satisfiability of non-standard formula really mean.