Consider countable alphabets and . Strings represent possible internal states of a computer; strings represent token sequences or code or programs for manipulating states. Without loss of generality, we focus on being the set of integers and representing a set of instructions of some universal programming language [14,72]. (The first universal programming language due to [14] was based on integers as well, but ours will be more practical.) and may be variable: new tokens may be defined by combining previous tokens, just as traditional programming languages allow for the declaration of new tokens representing new procedures. Since , substrings within states may also encode programs.
is a variable set of currently unsolved tasks. Let the variable denote the current state of task , with -th component on a computation tape (a separate tape holding a separate state for each task, initialized with task-specific inputs represented by the initial state). Since subsequences on tapes may also represent executable code, for convenience we combine current code and any given current state in a single address space, introducing negative and positive addresses ranging from to , defining the content of address as if and if . All dynamic task-specific data will be represented at nonpositive addresses (one code, many tasks). In particular, the current instruction pointer ip(r) of task (where can be found at (possibly variable) address . Furthermore, also encodes a modifiable probability distribution on .
Code is executed in a way inspired by self-delimiting binary programs [31,7] studied in the theory of Kolmogorov complexity and algorithmic probability [68,26]. Section 4.1 will present details of a practically useful variant of this approach. Code execution is time-shared sequentially among all current tasks. Whenever any has been initialized or changed such that its new value points to a valid address but , and this address contains some executable token , then will define task 's next instruction to be executed. The execution may change including . Whenever the time-sharing process works on task and points to the smallest positive currently unused address , will grow by one token (so will increase by 1), and the current value of will define the current probability of selecting as the next token, to be stored at new address and to be executed immediately. That is, executed program beginnings or prefixes define the probabilities of their possible suffixes. (Programs will be interrupted through errors or halt instructions or when all current tasks are solved or when certain search time limits are reached--see Section 3.2.)
To summarize and exemplify: programs are grown incrementally, token by token; their prefixes are immediately executed while being created; this may modify some task-specific internal state or memory, and may transfer control back to previously selected tokens (e.g., loops). To add a new token to some program prefix, we first have to wait until the execution of the prefix so far explicitly requests such a prolongation, by setting an appropriate signal in the internal state. Prefixes that cease to request any further tokens are called self-delimiting programs or simply programs (programs are their own prefixes). So our procedure yields task-specific prefix codes on program space: with any given task, programs that halt because they have found a solution or encountered some error cannot request any more tokens. Given a single task and the current task-specific inputs, no program can be the prefix of another one. On a different task, however, the same program may continue to request additional tokens.
is a variable address that can increase but not decrease. Once chosen, the code bias will remain unchangeable forever -- it is a (possibly empty) sequence of programs , some of them prewired by the user, others frozen after previous successful searches for solutions to previous task sets (possibly completely unrelated to the current task set ).
To allow for programs that exploit previous solutions, the universal instruction set should contain instructions for invoking or calling code found below , for copying such code into some state , and for editing the copies and executing the results. Examples of such instructions will be given in the appendix (Section A).