<p>How about <a href="https://programmingpraxis.com/2011/11/01/rip-john-mccarthy/" rel="nofollow noreferrer">McCarthy's original Lisp interpreter</a> (originally <a href="http://www-formal.stanford.edu/jmc/recursive.pdf" rel="nofollow noreferrer">here</a>)? It's universal, works on a natural encoding (a Lisp AST), doesn't rely on an external interpreter, and is about 20 lines.</p>

CC BY-SA 3.0
2016-12-16T09:23:48.663Z
2016-12-17T15:54:35.897Z
2016-12-17T15:54:35.897Z
pron
<p>Sure.  Write routines that compute each of Godel's <a href="http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition">primitive recursive functions</a>, 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 <a href="http://en.wikipedia.org/wiki/Primitive_recursive_function#Relationship_to_recursive_functions">here</a>.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-22T23:48:37.317Z
2010-10-22T23:48:37.317Z
Aaron Sterling
<p>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. </p>

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

CC BY-SA 2.5
2010-10-23T21:47:53.010Z
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.
Kaveh
CC BY-SA 2.5
2010-10-23T04:41:32.227Z
2010-10-23T04:41:32.227Z
Kaveh
<p>A universal function <code>u</code> can be written quite easily in a Haskell-like language (no side effects, higher-order functions), namely:</p>

<blockquote>
  <p><code>u f x = f x</code></p>
</blockquote>

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

<p>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.</p>

CC BY-SA 2.5
2010-11-08T22:33:33.140Z
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.
sdcvvc
CC BY-SA 2.5
2010-11-09T08:33:54.003Z
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.
Andrej Bauer
CC BY-SA 2.5
2010-11-07T19:54:51.500Z
2010-11-07T19:54:51.500Z
Andrej Bauer
<p>Check also <a href="https://tromp.github.io/cl/LC.pdf" rel="nofollow noreferrer">this paper</a> by John Tromp, using combinatory logic. An earlier writeup, apparently no longer available, was even neater.</p>

CC BY-SA 3.0
2010-10-23T03:48:24.747Z
2016-12-15T11:54:03.797Z
2016-12-15T11:54:03.797Z
Yuval Filmus
<p>Is there a short explicit construction of an <a href="http://en.wikipedia.org/wiki/Utm_theorem" rel="nofollow">universal recursive function</a>? 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.)</p>

CC BY-SA 2.5
2010-10-22T23:14:44.393Z
Question was originally asked at [SO](http://stackoverflow.com/questions/1797457), seems more appropiate here.
sdcvvc
CC BY-SA 2.5
2010-10-22T23:30:30.120Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-23T01:14:51.977Z
Not research level. Any interpreter for a Turing-complete language is a universal recursive function.
Warren Schudy
<lo.logic><computability><pl.programming-languages>
Writing universal recursive function
sdcvvc
# Writing universal recursive function

(Asked by: username_0 on 2010-10-22)

Is there a short explicit construction of an [universal recursive function](http://en.wikipedia.org/wiki/Utm_theorem)? 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.)

**Tags:** lo.logic, computability, pl.programming-languages
> **Comments:**
> **username_0**: Question was originally asked at [SO](http://stackoverflow.com/questions/1797457), seems more appropiate here.  
> **username_1**: 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.  
> **username_2**: Not research level. Any interpreter for a Turing-complete language is a universal recursive function.  

---

## 5 answers

### Answer by username_3 on 2016-12-16. Score: 1 | Accepted answer

How about [McCarthy's original Lisp interpreter](https://programmingpraxis.com/2011/11/01/rip-john-mccarthy/) (originally [here](http://www-formal.stanford.edu/jmc/recursive.pdf))? It's universal, works on a natural encoding (a Lisp AST), doesn't rely on an external interpreter, and is about 20 lines.


---

### Answer by username_4 on 2010-10-22. Score: 13

Sure. Write routines that compute each of Godel's [primitive recursive functions](http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition), 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](http://en.wikipedia.org/wiki/Primitive_recursive_function#Relationship_to_recursive_functions).

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.


---

### Answer by username_5 on 2010-10-23. Score: 10

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$.

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_6 on 2010-11-07. Score: 8

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.

> **Comments:**
> **username_0**: 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.  
> **username_6**: 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.  

---

### Answer by username_7 on 2010-10-23. Score: 5

Check also [this paper](https://tromp.github.io/cl/LC.pdf) by John Tromp, using combinatory logic. An earlier writeup, apparently no longer available, was even neater.


---

