I am interested in an enumeration of functions that starts with simple functions and progresses to more computationally expensive functions. Such an enumeration would enable to systematically try all useful functions for some task. For efficiency, it would be nice if the enumeration did not contain duplicate copies of the same function. Further, because the same function can be produced by multiple algorithms, for example $((a + b) + b)$ vs. $((b + b) + a)$, it would be nice to avoid also such semantic duplicates. The best would be if only the simplest algorithm giving each function would be in the enumeration.

Polynomials

A side step on the way to more general algorithms is polynomials. Here is a list of all polynomials with (your choice) integer or rational coefficients, optionally including negative coefficients. It is a long list as you will find out by scrolling. As a bonus, the index can be Gray coded to make successive polynomials differ only at one power of $x$. This makes their evaluation in the order of the enumeration faster.

Start at: Gray code: Include negative: Include rational:

You can jump to anywhere on the list as it is not generated recursively but is directly evaluated at any given value of the index. The construction of the enumeration uses the Stern–Brocot tree for integer-to-rational conversion and the following integer sequences from the Online Encyclopedia of Integer Sequences (OEIS):

the Gray code sequence A003188 (0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24, 25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16, 48, 49, 51, 50, 54, 55, 53, 52, 60, 61, 63, 62, 58, 59, 57, 56, 40, 41, 43, 42, 46, 47, 45, 44, 36, 37, 39, 38, 34, 35, 33, 32, 96, 97, 99, 98, 102, 103, 101, ...) that changes by only one bit between successive indexes and contains all nonnegative integers once,

the triangle sequence A002260 (1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...) minus 1, which gives an interleaving of bits belonging to coefficients of different powers of $x$, and

an interleaving of nonpositive and positive integers A001057 (0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6, 7, -7, 8, -8, 9, -9, 10, -10, 11, -11, 12, -12, 13, -13, 14, -14, 15, -15, 16, -16, 17, -17, 18, -18, 19, -19, 20, -20, 21, -21, 22, -22, 23, -23, 24, -24, 25, -25, 26, -26, 27, -27, 28, -28, 29, -29, 30, -30, 31, -31, ...) to convert from nonnegative integers to integers.

To convert positive integers to positive rational numbers the Calkin–Wilf tree or the Stern–Brocot tree can be used. There are others. The Calkin–Wilf tree starts with the number $\frac{1}{1}$. This and every other number $\frac{a}{b}$ in the tree branches to two other numbers $\frac{a + b}{b}$ and $\frac{a}{b + a}$. The Stern–Brocot tree is also a binary tree, but its construction is a bit different. Each subtree of the Stern–Brocot tree is associated with a triplet $(\frac{c}{d}, \frac{a}{b}, \frac{e}{f})$ where $\frac{a}{b}$ is the root node of the subtree and $\frac{c}{d}$ and $\frac{e}{f}$ are tight bounds for all of its nodes. The subtree has two subtrees rooted at the branches of its root node. These are associated with triplets $(\frac{c}{d}, \frac{a+c}{b+d}, \frac{a}{b})$ and $(\frac{a}{b}, \frac{a+e}{b+f}, \frac{e}{f})$. The full tree is associated with the triplet $(\frac{0}{1}, \frac{1}{1}, \frac{1}{0})$, citing bounds of zero and infinity. Because the Stern–Brocot tree is a binary search tree, it will also be easy to find any given polynomial (or its approximation if it has irrational coefficients) in the enumeration. These trees do not have semantic duplicates such as $\frac{2}{4}$ is a duplicate of $\frac{1}{2}$, and will in fact list all rational numbers in their most simple form.

In the integer-to-rational conversion, the most significant set bit of the integer is found and the less significant bits decide which rational number tree branches are taken. If the integer is signed, the resulting rational number inherits its sign and only the absolute value is converted.

For interleaving of bits I also tried the ruler function A001511 but to my taste it gave too large coefficients for the smallest powers of $x$, relative to the higher powers. At the limit of large numbers, the currently used sequence A002260 allocates an equal proportion of bits to different powers of $x$.

The enumeration is valid: no two polynomials in the enumeration are equal, and any polynomial will be in the list if its coefficients are in the chosen set of numbers. But this is only one of infinitely many valid enumerations. Just as an example, using or not using the Gray code results in two different enumerations that are both valid. The choice of the rational number tree has a similar effect.

Sorting by complexity

The above list of polynomials is not sorted by increasing algorithmic complexity. For example $1 - 2x + x^2 = (1+x)^2$ is found later on the list than the irreducible polynomial $1 + x + x^2 = 1 + (1 + x)x$, which is slower to calculate in a fully sequential multiply-add-subtract integer computer. In a computer with infinitely many parallel units they both evaluate in 2 steps. Another pair of polynomials, one irreducible, is enumerated in the wrong order also for the infinitely parallel computer: $1 + 4x + 6x^2 + 4x^3 + x^4 = ((1+x)^2)^2$ and $1 + x + x^2 + x^3 + x^4$. The enumeration seems quite oblivious of any internal structure of the polynomials that can be used to speed up computations.

An enumeration that sorts the polynomials in increasing order of multiply-add-subtract steps is impossible. At the first level of such an ordering would be numerical constants and $x$ itself. There is an endless number of the constants so we would never see any polynomials requiring one or more steps. Skipping the first level completely we would only encounter the same problem at the second level, and so on. One solution would be to penalize also for the magnitude of constants, but this would neglect the likely fact that structured numbers (such as $255 = 2^{2^3}-1$) are more useful in algorithms than other numbers. But how should such structure be defined? Perhaps by forcing the function to generate its own numerical constants from simple basic components such as the numbers 0 and 1, by computation. A problem is that some efficient algorithms such as Fast Fourier Transform make use of irrational numbers even for rational inputs and outputs, and it may be that equal performance cannot be matched by rational-only algorithms. Similarly, if there is fast division available, it could also speed up computation of powers such as $x^{31} =xx(xx)\left(xx(xx)\right)\left[xx(xx)\left(xx(xx)\right)\right]\left\{xx(xx)\left(xx(xx)\right)\left[xx(xx)\left(xx(xx)\right)\right]\right\}/x$.