Infinite Computations, Convergence, Formal Describability

Most traditional computability theory focuses on properties of halting programs. Given an MTM or EOM or GTM T with halt instruction and $p,x \in B^*$, we write

T(p)=x (3)

for ``p computes x on T and halts''. Much of this paper, however, deals with programs that never halt, and with TMs that do not need halt instructions.

Definition 2.1 (Convergence)   Let $p \in B^{\sharp}$ denote the input string or program read by TM T. Let T_t(p) denote T's finite output string after t instructions. We say that p and p's output stabilize and converge towards $x \in B^{\sharp}$ iff for each n satisfying $0 \leq n \leq l(x)$ there exists a postive integer t_n such that for all $t \geq t_n$: T_t(p)_n = x_n and $l(T_t(p)) \leq l(x)$. Then we write

$$T(p) \leadsto x.$$ (4)

Although each beginning or prefix of x eventually becomes stable during the possibly infinite computation, there need not be a halting program that computes an upper bound of stabilization time, given any p and prefix size. Compare the concept of computability in the limit [#!Gold:65!#,#!Putnam:65!#,#!Freyvald:74!#] and [#!Greg:57!#,#!Mostowski:57!#].

Definition 2.2 (TM-Specific Individual Describability)   Given a TM T, an $x \in B^{\sharp}$ is T-describable or T-computable iff there is a finite $p \in B^*$ such that $T(p) \leadsto x$.

Objects with infinite shortest descriptions on T are not T-describable.

Definition 2.3 (Universal TMs)   Let C denote a set of TMs. C has a universal element if there is a TM $U^C \in C$ such that for each $T \in C$ there exists a constant string $p_T \in B^*$ (the compiler) such that for all possible programs p, if $T(p) \leadsto x$ then $U^C(p_T p) \leadsto x$.

Definition 2.4 (M, E, G)   Let M denote the set of MTMs, E denote the set of EOMs, G denote the set of GTMs.

M,E,G all have universal elements, according to the fundamental compiler theorem (for instance, a fixed compiler can translate arbitrary LISP programs into equivalent FORTRAN programs).

Definition 2.5 (Individual Describability)   Let C denote a set of TMs with universal element U^C. Some $x \in B^{\sharp}$ is C-describable or C-computable if it is U^C-describable. E-describable strings are called enumerable. G-describable strings are called formally describable or simply describable.  

Example 2.1 (Pseudorandom universe based on halting problem)   Let x be a universe history in the style of Example 1.1. Suppose its pseudorandom generator's n-th output bit PRG(n) is 1 if the n-th program of an ordered list of all possible programs halts, and 0 otherwise. Since PRG(n) is describable, x is too. But there is no halting algorithm computing PRG(n) for all n, otherwise the halting problem would be solvable, which it is not [#!Turing:36!#]. Hence in general there is no computer that outputs x and only x without ever editing some previously computed history.

Definition 2.6 (Always converging TMs)   TM T always converges if for all of its possible programs $p \in B^{\sharp}$ there is an $x \in B^{\sharp}$ such that $T(p) \leadsto x$.

For example, MTMs and EOMs converge always. GTMs do not.

Definition 2.7 (Approximability)   Let 0.x denote a real number, $x \in B^{\sharp} \backslash \{ \lambda \}$. 0.x is approximable by TM T if there is a $p \in B^*$ such that for each real $\epsilon > 0$ there exists a t₀ such that

$$\mid 0.x - 0.T_t(p) \mid < \epsilon$$

for all times $t \geq t_0$. 0.x is approximable if there is at least one GTM T as above -- compare (2).

Lemma 2.1   If 0.x is approximable, then x is describable, and vice versa.

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI