Example of function which is not computable

Question

I am looking for a concrete example of a function $$f: N^k \rightarrow N$$ $$(n_1, n_2, \cdots n_k) \mapsto f(n_1, n_2, \cdots n_k)$$ which is not computable.

Source: Computability, An introduction to recursive function theory by Nigel Cutland Cambridge UP 1980 Chapter 4 Numbering computable functions Theorem 2.6 There is a total unary function that is not computable.

Answer 1

I am pleased to inform you that you can stop looking; it is well known that such a function cannot exist. The point is that URMs are more powerful computers (in a sense that can be made mathematically precise) than the primitive recursive functions. That is, programs on URMs can simulate any primitive recursive functions; i.e. every primitive recursive function is URM computable.

More powerfully, there is a universal machine which can simulate any algorithm (according to the Church-Turing thesis).

Edit:

Since you updated your question to remove the requirement that the function be primitive recursive, I am updating my answer.

The function constructed in the theorem you cite (Theorem 2.6 of Chapter 4 of Cutland's book) is a good (and I would even say, 'concrete') example of an non-computable function.

Note that most functions from $\mathbb{N}$ to $\mathbb{N}$ are incomputable. However, (roughly speaking) most such functions that arise in mathematics are computable.

Answer 2

You have a misunderstanding of what a "primitive recursive function" is. Cutland indeed proves nicely the existence of a total function which is non-computable; however, it is not primitive recursive!

Cutland himself does not state anywhere that his function is recursive; only that it is total.

Concrete examples of total, uncomputable function are easy: The most famous is the halting problem, where the input is a macine/input pair $(M,x)$ and the output is 0 or 1, depending on whether $M$ halts on $x$ or not (there are some variations in this definition but all in the same spirit).

I highly suggest to avoid Cutland's book as your intro into the subject. His method is presentation is "old school" and needlessly difficult, in my opinion. Michael Sipser's book is a much more modern and and friendly introduction.