Formal Setup and Notation

Unless stated otherwise or obvious, to simplify notation, throughout the paper newly introduced variables are assumed to be integer-valued and to cover the range implicit in the context. Given some finite or countably infinite alphabet $Q=\{Q_1,Q_2, \ldots \}$, let $Q^*$ denote the set of finite sequences or strings over $Q$, where $\lambda$ is the empty string. Then let $q,q^1,q^2, \ldots \in Q^*$ be (possibly variable) strings. $l(q)$ denotes the number of symbols in string $q$, where $l(\lambda) = 0$; $q_n$ is the $n$-th symbol of string $q$; $q_{m:n}= \lambda$ if $m>n$ and $q_m q_{m+1} \ldots q_n$ otherwise (where $q_0 := q_{0:0} := \lambda$). $q^1q^2$ is the concatenation of $q^1$ and $q^2$ (e.g., if $q^1=abc$ and $q^2=dac$ then $q^1q^2 = abcdac$).

Consider countable alphabets $S$ and $Q$. Strings $s,s^1,s^2, \ldots \in S^*$ represent possible internal states of a computer; strings $q,q^1,q^2, \ldots \in Q^*$ represent token sequences or code or programs for manipulating states. Without loss of generality, we focus on $S$ being the set of integers and $Q := \{ 1, 2, \ldots, n_Q \}$ representing a set of $n_Q$ 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.) $Q$ and $n_Q$ 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 $Q^* \subset S^*$, substrings within states may also encode programs.

$R$ is a variable set of currently unsolved tasks. Let the variable $s(r) \in S^*$ denote the current state of task $r \in R$, with $i$-th component $s_i(r)$ on a computation tape $r$ (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 $q$ and any given current state $s(r)$ in a single address space, introducing negative and positive addresses ranging from $-l(s(r))$ to $l(q)+1$, defining the content of address $i$ as $z(i)(r) := q_i$ if $0 < i \leq l(q)$ and $z(i)(r) := s_{-i}(r)$ if $-l(s(r)) \leq i \leq 0$. All dynamic task-specific data will be represented at nonpositive addresses (one code, many tasks). In particular, the current instruction pointer ip(r) $:= z(a_{ip}(r))(r)$ of task $r$ (where $ip(r) \in {-l(s(r)), \ldots, l(q)+1})$ can be found at (possibly variable) address $a_{ip}(r) \leq 0$. Furthermore, $s(r)$ also encodes a modifiable probability distribution $p(r) = \{ p_1(r), p_2(r), \ldots, p_{n_Q}(r) \}$ $(\sum_i p_i(r) = 1)$ on $Q$.

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 $ip(r)$ has been initialized or changed such that its new value points to a valid address $\geq -l(s(r))$ but $\leq l(q)$, and this address contains some executable token $Q_i$, then $Q_i$ will define task $r$'s next instruction to be executed. The execution may change $s(r)$ including $ip(r)$. Whenever the time-sharing process works on task $r$ and $ip(r)$ points to the smallest positive currently unused address $l(q)+1$, $q$ will grow by one token (so $l(q)$ will increase by 1), and the current value of $p_i(r)$ will define the current probability of selecting $Q_i$ as the next token, to be stored at new address $l(q)$ 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.

$a_{frozen} \geq 0$ is a variable address that can increase but not decrease. Once chosen, the code bias $q_{0:a_{frozen}}$ will remain unchangeable forever -- it is a (possibly empty) sequence of programs $q^1q^2 \ldots$, 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 $R$).

To allow for programs that exploit previous solutions, the universal instruction set $Q$ should contain instructions for invoking or calling code found below $a_{frozen}$, for copying such code into some state $s(r)$, and for editing the copies and executing the results. Examples of such instructions will be given in the appendix (Section A).

Back to OOPS main page