-2
$\begingroup$

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.

  • 1
    @lewellen: Chaitin's constant is actually a family of constants, one for each universal machine. There is no canonical example, if that is what's desired; the choice of universal machine is arbitrary.2011-06-06

2 Answers 2

3

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.

  • 0
    OK, Quinn. You were right and were the first to answer. Thanks.2011-06-06
3

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.

  • 0
    Although, if memory serves, Cutland also doesn't get much beyond the halting problem. This is a common problem in undergraduate-level books.2011-06-05