OOPS on Universal Computers

Subsection 3.1 will start the formal description of OOPS by introducing notation and explaining program sets that are prefix codes. Subsection 3.2 will provide OOPS pseudocode. Subsection 3.3 will point out essential properties of OOPS and a few essential differences to previous work. The remainder of the paper (Sections $\geq$ 4) is about practical implementations of the basic principles on realistic computers with limited storage.

Table 1: Symbols used to explain the basic principles of OOPS (Section 3).

Symbol	Description
$Q$	variable set of instructions or tokens
$Q_i$	$i$-th possible token (an integer)
$n_Q$	current number of tokens
$Q^*$	set of strings over alphabet $Q$, containing the search space of programs
$q$	total current code $\in Q^*$
$q_n$	$n$-th token of code $q$
$q^n$	$n$-th frozen program $\in Q^*$, where total code $q$ starts with $q^1q^2 \ldots$
$qp$	$q$-pointer to the highest address of code $q=q_{1:qp}$
$a_{last}$	start address of a program (prefix) solving all tasks so far
$a_{frozen}$	top frozen address, can only grow, $1 \leq a_{last} \leq a_{frozen} \leq qp$
$q_{1:a_{frozen}}$	current code bias
$R$	variable set of tasks, ordered in cyclic fashion; each task has a computation tape
$S$	set of possible tape symbols (here: integers)
$S^*$	set of strings over alphabet $S$, defining possible states stored on tapes
$s^i$	an element of $S^*$
$s(r)$	variable state of task $r \in R$, stored on tape $r$
$s_i(r)$	$i$-th component of $s(r)$
$l(s)$	length of any string $s$
$z(i)(r)$	equal to $q_i$ if $0 < i \leq l(q)$ or equal to $s_{-i}(r)$ if $-l(s(r)) \leq i \leq 0$
$ip(r)$	current instruction pointer of task $r$, encoded on tape $r$ within state $s(r)$
$p(r)$	variable probability distribution on $Q$, encoded on tape $r$ as part of $s(r)$
$p_i(r)$	current history-dependent probability of selecting $Q_i$ if $ip(r)=qp+1$

Back to OOPS main page