# Writing universal recursive function [closed]

Is there a short explicit construction of an universal recursive function? All definitions I have seen involve numbering of Turing machines in some way, which is possible yet seems hard and unmanageable to write in a higher-level programming language (like Python, Haskell etc.)

• Question was originally asked at SO, seems more appropiate here. Oct 22, 2010 at 23:14
• My understanding is that what a universal recursive function does is exactly to give some numbering of recursive functions (or equivalently Turing machines) so that the result can be calculated from the index of a recursive function and the input. Therefore “a universal recursive function without numbering Turing machines” does not sound plausible to me. Oct 22, 2010 at 23:30
• Not research level. Any interpreter for a Turing-complete language is a universal recursive function. Oct 23, 2010 at 1:14

How about McCarthy's original Lisp interpreter (originally here)? It's universal, works on a natural encoding (a Lisp AST), doesn't rely on an external interpreter, and is about 20 lines.

Sure. Write routines that compute each of Godel's primitive recursive functions, and write a routine for an unbounded search operator. The set of functions you can compute this way is equivalent to the set of functions Turing machines can compute. More information here.

The downside is that any input to your universal program would need to be framed in terms of those simple operations. Of course, that is what compilers are for.

Any interpretor for any language which is Turing complete is a universal recursive function. There are interpretors for high-level languages like C++ or Python.

Godel numbering exists, but implicitly. For example, the C++ code computing a recursive function $g$ is an index for $g$.

• An interpretor for Turing Machines (or Register Machines, or recursive functions) is also a universal recursive function, and it is not difficult to implement them. I have implemented them in C++ some years ago, and I am pretty sure that it would be even simpler in Python. Use Google, there are many free simulators on the Internet, and some of them are even open-source. Oct 23, 2010 at 21:47

A universal function u can be written quite easily in a Haskell-like language (no side effects, higher-order functions), namely:

u f x = f x

The function u is universal because it accepts (the description of) a program f and an input tape x, and tells you the result of running f on x.

While this answer is not entirely serious, it does show that a compiler or an interpreter for a Haskell-like language already contains all the building parts needed for a universal function. The moral of the story is that time is better spent studying how compilers and interpreters work than to worry about implementing a universal function in terms of Turing machines.

• However, u takes a function - I'd call it a higher-order function. I'd like u to take an integer, or a regular algebraic datatype. I don't force any specific model of computation, as long as argument to u is tangible - for example, it can be serialized from/to a string. Nov 8, 2010 at 22:33
• On an actual machine (once the code is compiled) u takes a closure, which is a finite sequence of bytes. Even in the usual utm theorem the integer that u takes represent a function. Nov 9, 2010 at 8:33

Check also this paper by John Tromp, using combinatory logic. An earlier writeup, apparently no longer available, was even neater.