# Example of function which is not computable

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.

• Can you describe what URM-computable means? Every primitive recursive function is computable by a Turing machine. – Gadi A Jun 4 '11 at 18:54
• @ndrock1: Two points: First, having a map from the computable functions to the recursive functions that isn't surjective isn't enough to show that there are recursive functions that are not computable. Second, you completely missed my point. My point is that there aren't any recursive functions that are not computable and the book proves that there is some function that is not computable, not a recursive function that is not computable. – Apostolos Jun 4 '11 at 22:29
• The recent edit completely changed the meaning of this question; I have opened a thread at meta.math.stackexchange.com/questions/2304/… – Carl Mummert Jun 6 '11 at 15:16
• @ndroock1 Do you consider the function constructed in Theorem 2.6 concrete? – Quinn Culver Jun 6 '11 at 16:12
• @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. – Carl Mummert Jun 6 '11 at 19:44

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.

• See my edit. – nilo de roock Jun 4 '11 at 20:03
• @ndroock1 This is not what Theorem 2.6 of Cutland's book says. It merely says that some functions are not even URM computable. Note that the existence of such a function only relies on computability insofar as the set of computable functions is countable. – Quinn Culver Jun 5 '11 at 0:31
• @ndrock1 Moreover Theorem 2.6 has nothing to do with the primitive recursive functions. – Quinn Culver Jun 5 '11 at 0:32
• Or did you possibly confuse the fact that the same diagonal argument exhibited in Theorem 2.6 can be employed to show that there is a URM computable function that is not primitive recursive? – Quinn Culver Jun 5 '11 at 0:34
• OK, Quinn. You were right and were the first to answer. Thanks. – nilo de roock Jun 6 '11 at 14:24

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.

• @Gaudi. I will accept when I have confirmed this in both Sipser ( which is new to me ) and Cutland., thanks. - Can you please give arguments why Cutland is old school which I can use further? - I'll get back to this soon, after further study of the topic. – nilo de roock Jun 5 '11 at 8:12
• For one, his use of register machines and primitive recursive functions. This are computational models equivalent in power to Turing machines, but they are much more cumbersome. It is good to know them and have a better perspective, but only after grasping the basics of computability theory. – Gadi A Jun 5 '11 at 8:35
• @Gadi I like Cutland's book and think that it is better from the point of view of classical computability theory, which is still an active area of mathematical research; Sipser's is better from the point of view of computer science. Even though I prefer Turing machines, URMs are still nice and intuitively graspable. Cutland (in chapter 4, section 3) gives a nice introduction to Turing machines anyway and even sketches a proof of the fact that the two models of computation are equivalent. – Quinn Culver Jun 5 '11 at 14:43
• Yet I still believe that it is much easier to understand "classic" computability after understanding "modern" computability, and not vice versa. I also find that many ideas and proofs are simpler in the more "algorithmic" framework of modern computability (Kleene'e recursion theorem is a good example, in my opinion) – Gadi A Jun 5 '11 at 16:37
• @Gadi: I personally prefer register machines and primitive recursive functions for learning computability, over Turing machines, which I view as mostly a historical topic form the point of view of recursion theory. For example it is much more difficult to prove that some theory represents all computable functions if they are defined via Turing machines rather than primitive recursion and the $\mu$ operator. Sipser's book barely covers classical computability theory (which is about uncomputable sets). It seems we have opposite views about which method is the contemporary one. – Carl Mummert Jun 5 '11 at 21:06