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

not an easy question. I guess you have to start with a function generator which is able generate all functions one by one. This will result in an enumeration.

Since you have to deal with multiple endless dimensions... let's think about it.

Let's reduce the problem to functions with n parameters and the basic operations +, -, *, /.
Let's build all functions with only one operation:

a + a
a + b
a - a
a - b
a * a
a * b
a / a
a / b

I guess it is easy to see that some of these functions make more sense as others and some of them could be equal, but at least, it is a mapping which can be generated through a loop.

Now in the next iteration, one could easily add to each of these functions

• one of the already existing parameters with all operations
• a third parameter with all operations

Afterwards you have a huge list of functions for which you can repeat step two.

Since the is a function which estimates all more complex functions like sin and log (taylor series), these should be covered in this functions space too.

Does this help? Feel free to edit this post!

Just re-read your post. If you want to enumerate all programmatic functions and not only numeric once, I guess it will be more complex. I guess then it just would make sense to work with a mapping "function <-> number" by zipping the source of your function and treating the zip file as a large number. The other way around, you can try to unzip any number and see if it creates a useful function :-) But I guess you will have lots of number which are not even zip files.

But it would fullfill your requirement that for every function there is a number which represents it :-)

Answer 2

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 3

You can take any programming language such that you can determine whether something is a program or not, and list all programs in lexicographic order. To avoid at least a little of the combinatoric explosion, you can assign user-defined names (variables, functions, etc.) in a normalized form. Obviously, this is going to result in an immense number of functions, and it's not going to be easy to pick out which ones are actually useful. Any automatic method of trimming will either exclude some functions that you're actually going to want, or fail to trim the combinatoric explosion enough to be useful, or both.

The other disadvantage of this is that it's going to be very difficult to go from the number to the function: it's hard to find a better way of finding function 433,457,175,432,167,463 than to enumerate about four hundred quadrillion functions.

The other way is to encode a function into a number by mapping the symbols to numbers, and effectively concatenating them.

Assume that the symbols are +, -, :=, ==, <, if, then, endif, do, end_do_condition, enddo, and a statement delimiter. That's 11 symbols right there, without variables, for a pretty minimal set that doesn't include anything like a function call, and requires that you multiply and divide yourself. (I'm not actually sure this would work without a logical operator or two.) Add five variable names, and you've got a programming language with 4-bit characters. This means that a maximum of sixteen characters will fit into a 64-bit unsigned integer.

Once you've got this, all the possible relations between functions are going to be representable as an arithmetic relation, but an immensely complicated one that will be far to complex to get right in practice.

In short, while this is theoretically possible, it's going to be far too clumsy in practice. It would probably be easier to write an interpreter for a functional language in your nonfunctional language of choice.

Answer 4

To write such a function, one can take any Turing-complete language (programming language compiler, lambda calculus, Turing machines...) and enumerate all programs

I'm not very sure if that can be done at all... It feels like it goes against the Turing-Church thesis. In order to enumerate all programs, first you need an algorithm that determines which programs are valid and which ones aren't, and that's impossible... Unless you don't care about that and allow incorrect programs in your language.

But maybe the Godelization of a formal system could help you... I'd try with Lisp, having the code as data could help a lot.

Answer 5

Not sure I understand. One thing though - you can't enumerate all possible computable functions. Short answer: because otherwise there will be a universal antivirus. Long answer: because if there was such an enumeration, you would have in that set also the function that computes the enumeration itself. Like Russel's paradox.

A different answer to your question would be - you want to ``list'' all possible computable functions; to do that, you might want to represent them as prime numbers, and use their composition as multiplication. This would guarantee uniqueness. Factorisation will give you the reverse function.

Answer 6

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.

Answer 7

As Pascal said, what you want is a interpreter, but one can do even better: Use the processor as interpreter directly.

Feed the number N (say, as some big int array) directly to a buffer and execute this buffer as machinecode.

For every possible function you computer is able to execute there exists a N. Unfortunatly. not every N is a valid program (this wasn't requested) or the terminating program (which isn't possible).

On the other hand, this function will produce such gems as World of Warcraft, Microsoft Office 17 including Service Pack 6 and Windows 9.