When we talk about recursively self-improving AI, the word "recursive" there is close enough to being literal rather than metaphoric that we glide over it without asking precisely what it means.

But it's not literally recursion—or is it?

The notion is that an AI has a function optimize(X) which optimizes itself. But it's recursion in the sense of modifying itself, not calling itself. You can imagine ways to do this that would use recursion—say, the paradigmatic executable that rewrites its source code, compiles it, and exec's it—but you can imagine many ways that would not involve any recursive calls.

Can we define recursive self-improvement precisely enough that we can enumerate, explicitly or implicitly, all possible ways of accomplishing it, as clearly as we can list all possible ways of writing a recursive function? (You would want to choose one formalism to use, say lambda calculus.)

To see why this is important, consider this set of LISP functions:

[1]> (defun f(x) (g x))
F
[2]> (defun g(x) (f x))
G
[3]> (f 0)

*** - Lisp stack overflow. RESET

The composition of f and g is a recursive function, though neither f nor g is itself recursive. This is analogous to two AIs, neither of which wishes to nor can modify itself, but each of which can modify the other. I can imagine that AI #1 wants to use AI #2 for some task, and tweaks its code to improve it. Meanwhile AI #2 wants to use AI #1 for something else, and tweaks its code to improve it. And so on. The effect is something like recursive self-improvement of both AIs. Without being guided by the analogy between recursive functions and recursive self-improvement, it would be easy to overlook this possibility.

The notion of an AI which can rewrite its own source code is just one special case, which is both unlikely and poorly-defined. Unlikely, because lots of programmers already write self-modifying code, and they don't give the program a text file with its source code. Poorly defined, because many languages and computational architectures blur the distinction between code and data.

Once we try to be specific about what it means, we see there are many different ways of accomplishing it. We could provide a LISP program with a pointer to the data structure of the running program. We could write Perl code that can read and modify functions defined in the symbol table. We could write Prolog programs that assert new rules.

Do all these different ways have the same self-improvement power, in a way analogous to how all good programming languages are Turing-complete? For instance, imagine one logic program that can rewrite its facts, another that can also add new rules, a third that can also delete rules, and a fourth that can also rewrite its logic. Are these different enough that we should consider them as different cases when we enumerate the methods of recursive self-improvement?