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$$ (1)

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.$$ (2)

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 [19,33,15] and [20,32].

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$.

According to this definition, objects with infinite shortest descriptions on $T$ are not $T$-describable, reflecting the fact that we will never ever be able to produce a complete $T$-based description of such an object.

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 computably enumerable (c.e.). G-describable strings are called formally describable or simply describable.

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_0$ 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.

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

Henceforth we will exchangeably use the expressions approximable, describable, computable in the limit.