Non-computable but easily described arithmetical functions

Question

I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted here.

Answer 1

A function $f:\mathbb{N}\to\mathbb{N}$ is computable if and only if the graph of $f$ is $\Sigma_1$ definable in the arithmetic hierarchy, which means that $f(x)=y\iff \exists n\ \varphi(x,y,n)$, where $\varphi$ involves only bounded quantifiers. Thus, the essence of computation is that it is the search for an arithmetic witness $n$ of some primitive property.

Many functions, however, are easy to describe but cannot be expressed in this simple form. Here are some examples:

• The characteristic function of the set of theorems of your favorite axiomatization of mathematics, such as PA or ZFC; this is the function that correctly labels assertions as theorem or non-theorem. We may view assertions directly as syntactic strings of symbols or we may code them as numbers if you wish (and this is surely a cosmetic difference). While we can recognize theorems by their proofs, we provably have in principle no computable way to recognize a non-theorem.

• The truth function, which correctly labels the statements of arithmetic as true or false, is not computable. This function is not in the arithmetic hierarchy, but it exists at the entry level $\omega$ to the hyperarithmetic hierarchy.

• The halting problem function, which correctly labels program-input pairs as halting or non-halting, is easy to describe, but not computable.

• The Tiling function, which given any finite set of polygonal tiles, outputs the size $k$ of the largest $k\times k$ square that can be tiled by them, or $0$ if they tile the entire plane.

• The Conjugate function, which given two words in a finite group presentation, correctly states whether they are conjugate or not.

• The Solve function, which given a polynomial over the integers in several variables, outputs the list of smallest-norm integer solutions (giving the empty list if there are none). This is not computable by the MRDP solution to Hilbert's 10th problem. The positive instances are computable, of course, as they are witnessed by their corresponding calculation, but the empty list provably cannot be witnessed in a finitary way.

• The Tot function, which correctly labels Turing machine programs as total or strictly partial.

• The Empty function, which labels Turing machine programs as empty or non-empty, depending on whether they accept an input.

• An uncountable supply of examples is provided by Rice's Theorem, which asserts that no non-trivial property of the c.e. sets is computable from their programs. Thus, if $W_e$ is the set enumerated by program $e$, then for any family of sets ${\cal A}$ which contains some but not all $W_e$, the characteristic function of the set of programs $\{ e | W_e\in{\cal A}\}$ is not computable. For example, the functions that decide whether program $e$ enumerates a connected graph, or whether this set contains any primes, or whether it is eventually periodic, or whether it exhibits any other property that holds of some but not all programs, are all non-computable.

Answer 2

Joel and John have given lots of important examples; here is a curiosity:

John Conway invented the Turing complete language FRACTRAN. In this language, a program is simply a a finite sequence of fractions $p_1/q_1$, $p_2/q_2$, ..., $p_r/q_r$. Given an integer $n$, FRACTRAN multiplies $n$ by the first $p_i/q_i$ for which $q_i$ divides $n$. It does this repeatedly until no such $i$ exists, then it halts.

For any FRACTRAN program $(p_1/q_1, \ldots, p_r/q_r)$, consider the function $f$ which returns $1$ if the program halts and $0$ if it does not. This function can be rewritten as a simple piecewise-linear recurrence:

$f(n)=1$ if none of the $q_i$ divides $n$.
If $q_i$ is the first $q_i$ which divides $n$, then $f(n)=f(n p_i/q_i)$.
If $f(n)$ is not forced by the above conditions, then $f(n)=0$.

Now take a program for which it is undecidable, given an input $n$, whether or not it will halt. Would you agree that this is an easily described arithmetic function, if it were written out as a recurrence like this?

Answer 3

There are some easily-described noncomputable functions, if you are willing to accept functions that take finite objects other than numbers as inputs. The "objects" I'm referring to represent instances of Turing undecidable problems, such as those given as answers to this MO question. For example, you could take the function $f$ whose inputs are polynomials $p$ with integer coefficients, and defined by

$f(p)=1$ if $p=0$ has an integer solution, $f(p)=0$ otherwise.

This function is noncomputable because of Matiayasevich's theorem.

If you insist on a function with integer inputs, then in this case you have to encode each polynomial by an integer (and you also have to express the relation "$p=0$ has an integer solution" arithmetically). It is not hard to do, but not so natural or so easily-described. Unfortunately, this is always the case -- it seems that arithmetic is not such a natural language for expressing computability.

[Added later] I am assuming that "arithmetical functions" are those definable in the language of Peano Arithmetic, which has the usual logical symbols, variables, the constant 0, and the symbols $S$ (for successor), $+$, $\times$, and $=$.