Formal Details of a Particular Gödel Machine

Unless stated otherwise or obvious, throughout the paper newly introduced variables and functions are assumed to cover the range implicit in the context. $B$ denotes the binary alphabet $\{ 0, 1 \}$, $B^*$ the set of possible bitstrings over $B$, $l(q)$ denotes the number of bits in a bitstring $q$; $q_n$ the $n$-th bit of $q$; $\lambda$ the empty string (where $l(\lambda)=0$); $q_{m:n}= \lambda$ if $m>n$ and $q_m q_{m+1} \ldots q_n$ otherwise (where $q_0 := q_{0:0} := \lambda$). Occasionally it may be convenient to consult Figure 1 below.

Figure 1: Storage snapshot of a not yet self-improved example Gödel machine, with the initial software still intact. See text for details.

Back to Goedel Machine Home Page