All the simple examples of undecidable problems that I know deal with symbolic computation or calculation. For example, the halting problem, whether Diophantine equations have solutions, the word problem for groups, the Post correspondence problem. The post An example of an easy to understand undecidable problem provides some other examples.

Any of these can be turned into an undecidable decision problem for a subset of $\Bbb N$ by suitably encoding the problem instances as numbers.

I would like an example of undecidable subset of $\Bbb N$ that is presented directly, defined in terms of some predicate $\phi$ that applies as directly as possible to the arithmetic properties of the numbers themselves

rather than something like “$\phi(n)$ holds if $n$ is the index of a Turing machine $\#n$ for which…” or “$\phi(n)$ means that $n$, considered as representing a Lisp program encoded in ASCII…”.

Is there such an example?

(This question is similar in spirit to the one that asks if there is an undecidable theorem of arithmetic that isn't of the highly artificial type that is constructed by Gödel's incompleteness theorem. There the usual examples are Goodstein's theorem or the Parris-Harrington theorem.)

  • 2
    $\begingroup$ Would you mind to define "artificial" and "natural", please? $\endgroup$ – Professor Vector Jun 30 at 18:44
  • 1
    $\begingroup$ You can't expect an answer more precise than the question. And so far, there isn't a question that would qualify as "mathematics," sorry! $\endgroup$ – Professor Vector Jun 30 at 18:49
  • 1
    $\begingroup$ @ProfessorVector Searching for natural examples on MathOverflow produces 93 questions with 61 answers. $\endgroup$ – MJD Jun 30 at 18:57
  • 3
    $\begingroup$ We can whip up a polynomial in variables $x_1,...,x_n, y$ (for some big-but-not-too-big $n$) such that the set of $y$ for which $x_1,...,x_n$ exist making the polynomial zero is incomptable. This is about as arithmetic as it gets - it immediately has the form $$\exists x_1,...,x_n(a_1x_1^{i_{1,1}}x_2^{i_{1,2}}...x_n^{i_{1,n}}y^{j_1}+...+a_mx_1^{i_{m,1}}x_2^{i_{m,2}}...x_n^{i_{m,n}}y^{j_m}=0)$$ for appropriate $a_u, i_{u,v},j_k$. Does this count? $\endgroup$ – Noah Schweber Jun 30 at 19:14
  • 2
    $\begingroup$ @MJD Yes, you get that from the MRDP theorem. The MRDP theorem says that every c.e. set is Diophantine; so, just pick your favorite noncomputable set and rephrase it as a Diophantine set. As to what $n$ is, it's not too big: for example, Theorem $1.1(i)$ here together with the four squares theorem gives an upper bound of $36$, and I believe the actual current best upper bound is around $12$. $\endgroup$ – Noah Schweber Jun 30 at 19:50

By the MRDP theorem, every c.e. set is Diophantine. Thus, there is some Diophantine equation $P(x_1,...,x_n,y)=0$ such that $$\{y:\exists x_1,...,x_n(P(x_1,...,x_n,y)=0)\}$$ is incomputable (just pick your favorite incomputable c.e. set). Of course this $P$ will be quite complicated, but perhaps surprisingly it's not too bad - I don't know the current state of the art exactly, but see here (and in particular, from Theorem $1.1$ we can extract an upper bound of $36$ on the number of $x$-variables needed).

Of course there's coding going on under the hood, but the sentence itself doesn't look particularly conspicuous. (In particular it doesn't have any complicated quantifier structure.)

| cite | improve this answer | |
  • $\begingroup$ Is "c.e." short for "computably enumerable"? $\endgroup$ – MJD Jul 1 at 4:52
  • $\begingroup$ @MJD Yes. We suffer from an overabundance of synonyms ("c.e.," "computably enumerable," "r.e.," "recursively enumerable," "semidecidable," and "recognizable" are all synonymous). $\endgroup$ – Noah Schweber Jul 1 at 5:16
  • $\begingroup$ Thanks. That Sun paper is really interesting. $\endgroup$ – MJD Jul 1 at 12:38

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.