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.)
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Question was originally asked at SO, seems more appropiate here. $\endgroup$– sdcvvcOct 22, 2010 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 ItoOct 22, 2010 at 23:30
-
3$\begingroup$ Not research level. Any interpreter for a Turing-complete language is a universal recursive function. $\endgroup$– Warren SchudyOct 23, 2010 at 1:14
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Oct 22, 2010 at 23:48
$\begingroup$
$\endgroup$
1
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$.
-
$\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$– KavehOct 23, 2010 at 21:47
$\begingroup$
$\endgroup$
2
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.
answered Nov 7, 2010 at 19:54
-
$\begingroup$ However,
utakes a function - I'd call it a higher-order function. I'd likeuto take an integer, or a regular algebraic datatype. I don't force any specific model of computation, as long as argument touis tangible - for example, it can be serialized from/to a string. $\endgroup$– sdcvvcNov 8, 2010 at 22:33 -
$\begingroup$ On an actual machine (once the code is compiled)
utakes a closure, which is a finite sequence of bytes. Even in the usual utm theorem the integer thatutakes represent a function. $\endgroup$ Nov 9, 2010 at 8:33
$\begingroup$
$\endgroup$
0
Check also this paper by John Tromp, using combinatory logic. An earlier writeup, apparently no longer available, was even neater.
answered Oct 23, 2010 at 3:48