Background: I have been studying some decidability results in number theory. In doing so, I have always assumed there was no need for me to study pedantic definitions of decidability using Turing machines or similar, since the naive idea of an algorithm ('something which you could program a computer to do') seemed to be enough to understand most proofs. I now notice that this intuitive understanding might lead me to false conclusions. /Background

Consider the following problem: to find an algorithm which - on input a polynomial with coefficients in $\mathbb{Z}$ and an arbitrary number of variables - outputs YES if and only if the polynomial has an integer root, NO otherwise (Hilbert's 10th problem).

By a theorem of Matiyasevich, this problem is unsolvable, in that such an algorithm does not exist. The following naive approach of mine would imply that such an algorithm does exist:

  • Clearly if a polynomial $f \in \mathbb{Z}[X_1, \ldots, X_n]$ has a root $\bar{z} = (z_1, \ldots, z_n) \in \mathbb{Z}^n$ then there is a proof for this in the theory of arithmetic (axiomitized by the Peano axioms, for example). Indeed: just calculate $f(\bar{z})$ and note that this equates to zero. It follows by Gödel's Completeness Theorem that also if $f$ has no root in $\mathbb{Z}^n$, there is a proof of this fact in the first-order theory of arithmetic.
  • Given a finite sequence of symbols from the language of arithmetic (logical symbols, $+, -, \cdot, 0, 1$ and a symbol $\downarrow$ indicating that a new line should begin), there exists an algorithm which checks whether this sequence is a valid proof in the theory of arithmetic.
  • The number of finite sequences of symbols in the language of arithmetic is countable. Even stronger: a bijection $\varphi$ from $\mathbb{N}$ to this set can be constructed explicitly as the number of symbols is finite, so we can just list all sequences with only 1 symbol, then all sequences with 2 symbols and so on.
  • Now define the following algorithm: for $m = 1,2,3, \ldots$, verify whether $\varphi(m)$ is a valid proof. If so, check if the last line spells "$f$ has a root in $\mathbb{Z}^n$" or "$f$ has no root in $\mathbb{Z}^n$. If so, output YES or NO accordingly. If not, continue with $m+1$ instead of $m$.
  • By my first point, the above algorithm always terminates.

Where did I make a mistake, i.e. what part of my argument violates the strict definition of what an algorithm is? Unless I am overlooking something, it seems like something I could make a computer do if my programming skills would allow it.

  • $\begingroup$ Can you elaborate on this for a second: "It follows by Gödel's Completeness Theorem that also if ff has no root in Zn, there is a proof of this fact in the first-order theory of arithmetic." $\endgroup$
    – ASKASK
    Nov 12 '17 at 0:48
  • 1
    $\begingroup$ Just remember that Godel's completeness theorem says that a sentence that is satisfied by every model is provable. In your case, you in fact only looked at one model, namely the (conventionally called) standard one. $\endgroup$
    – user21820
    Nov 12 '17 at 6:15

The problem is that it's possible $f$ has no integer roots, but there is no proof of this fact (in whatever theory of arithmetic you are using). You're right that if $f$ does have a root, then you can prove it by just plugging in that root. But if $f$ does not have a root, that fact need not be provable. In that case, your algorithm will never halt.

  • 5
    $\begingroup$ Moreover, as a corollary to the actual solution of H10, we know that for any effective formal system that only proves true statements, there will be some integer polynomial that has no integer roots, but so that the system does not prove that the polynomial has no integer roots. In other words the "possibility" here is a certainty if we look at effective, true theories. $\endgroup$ Nov 11 '17 at 18:31
  • 1
    $\begingroup$ Then my problem is with Gödel's completeness theorem. My reasoning: if there is no proof for the non-existence of a root, then there would exist a model of arithmetic in which there is a root. But then we could prove that there is a root? $\endgroup$
    – Bib-lost
    Nov 11 '17 at 18:33
  • 9
    $\begingroup$ @Bib-lost: no, because that model might be a non-standard model, and the root in the model might not correspond to an actual integer - the root might correspond to a nonstandard element of the model. $\endgroup$ Nov 11 '17 at 18:34
  • 2
    $\begingroup$ Aha, that is somewhat reassuring. So in a non-standard model there might also exist polynomials which have roots, but of which we can not prove that they have roots. Interesting. Thanks for the quick response! $\endgroup$
    – Bib-lost
    Nov 11 '17 at 18:34
  • 2
    $\begingroup$ @Bib-lost Similarly, there are models of PA which "think" that PA is inconsistent, in the sense that there is a "natural number" coding a proof of $0=1$ from the PA-axioms; but this "natural number" is in fact nonstandard. $\endgroup$ Nov 11 '17 at 18:37

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.