How to write an enumeration of all computable functions?

Question

Motivation: I'd like to be able to use toy functional programming in languages without first-order functions, by using natural numbers instead of functions.

A universal function is a function f : N -> (N -> N), equivalently f : N * N -> N that enumerates all possible computable functions. In other words, there's a number k such that f(k) is the squaring function, there's a number j such that f(j) is the n-th prime function etc.

To write such a function, one can take any Turing-complete language (programming language compiler, lambda calculus, Turing machines...) and enumerate all programs. I'd like to allow not only evaluation, but also operations on functions like addition, composition, currying. For example, given indices of two functions f,g I'd like to know what is the index of the function f+g, or f composed with g. This would allow "toy functional programming".

What is a good way to write such code library? I'm not looking for a minimalistic Turing tarpit that will struggle to compute factorial of 10, nor I don't want to write an advanced compiler. It should have some basic functions like addition and possibility to write loop, but not much more.

Solutions in all high-level languages are welcome. Pseudocode, Haskell and Python are preferred. You can assume arbitrary precision arithmetic. Using eval or similar is not allowed.

Clarification: Enumerated functions will consist of all partial recursive (computable) ones - this includes functions that don't halt on some inputs. The universal function will hang in that cases; of course this is unavoidable. See also: m-recursive functions - http://en.wikipedia.org/wiki/Μ-recursive_function.

Answer 1

What you want is called an interpreter.

First, any enumeration with the properties you want is not going to fit the interesting functions you want to manipulate in the first 2^32, or even the first 2^64, integers. So you will need larger integers, allocated somewhere in memory and referenced through a pointer.

Why not use arrays of chars (strings) representing program in any existing syntax then? Consider such a string as an integer if that makes you happy. The number of the function to compute f1()+f2() is the string made of (representation of f1), "+", and (representation of f2). You get the idea...

What this approach does not have is unicity of the representation of a function, that was maybe implied in your question (I am not sure). What I am sure of is that unicity of representation is incompatible with having simple, or even computable, composition operations on function representations -- For instance, there would be an easy solution to the Halting problem if it wasn't the case.

Answer 2

While it is not too hard to enumerate all possible expressions in some language, you won't be able to restrict these to those expressions that denote terminating functions.

But if you are not interested in termination, using combinators (with some arithmetic primitives thrown in for usefulness) might be the best way, since you avoid introducing variable names that way.