2 added 35 characters in body; added 60 characters in body; deleted 5 characters in body

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, correctly outputs tiles-the-planethe size $k$ of the largest $k\times k$ sqaure that can be tiled by them, or does-not-tile-the-plane$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 does not hold (or fail) holds of some but not all progamsprograms, are all non-computable.

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, correctly outputs tiles-the-plane or does-not-tile-the-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}$, 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 does not hold (or fail) of all progams, are all non-computable.