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.)
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
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$.
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
u is universal because it accepts (the description of) a program
f and an input tape
x, and tells you the result of running
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.
Check also this paper by John Tromp, using combinatory logic. An earlier writeup, apparently no longer available, was even neater.