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.



Non-computable but easily described arithmetical functions
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](http://en.wikipedia.org/wiki/Rice%27s_theorem), 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$ sqaure 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](http://en.wikipedia.org/wiki/Rice%27s_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.


