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?
At the heart of this question is some concept of resource permission that I'm trying to nail down--that is, agent X has 'self-modified' into agent Y iff agent Y has the same hardware resources that agent X had. This distinguishes self-modification from emulation, which is important; humans have limited self-modification, but with a long paper tape we can emulate any program.
A proposed measure: Define the 'emulation penalty' of a program that could execute on the AI's machine as the ratio of the runtime of the AI's fastest possible emulation of that program to the runtime of the program executing directly on the machine. The maximum emulation penalty over all possible programs puts at least an lower bound on the AI's ability to effectively self-modify into any possible agent.
An AI that can write and exec assembly would have a max emulation penalty of 1; one that can write and exec a higher-level language would probably have 10-100 (I think?); and one that could only carry out general computation by using an external paper tape would have a max emulation penalty in the billions or higher.
Therefore, for a computer in Greg Egan's Permutation City, emulation is self-modification?