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.

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:



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 piecewiselinear recurrence:
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? 


There are some easilydescribed 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 easilydescribed. 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 $=$. 

