9
$\begingroup$

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

$\endgroup$

closed as off-topic by Andrej Bauer, Jan Johannsen, Emil Jeřábek, Sasho Nikolov, Mohammad Al-Turkistany Dec 18 '16 at 19:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Andrej Bauer, Jan Johannsen, Emil Jeřábek, Sasho Nikolov, Mohammad Al-Turkistany
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Question was originally asked at SO, seems more appropiate here. $\endgroup$ – sdcvvc Oct 22 '10 at 23:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Oct 22 '10 at 23:30
  • 3
    $\begingroup$ Not research level. Any interpreter for a Turing-complete language is a universal recursive function. $\endgroup$ – Warren Schudy Oct 23 '10 at 1:14
1
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 23 '10 at 21:47
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – sdcvvc Nov 8 '10 at 22:33
  • $\begingroup$ 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. $\endgroup$ – Andrej Bauer Nov 9 '10 at 8:33
5
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.