Next: Formally Describable Functions Up: Preliminaries Previous: Turing Machines: Monotone TMs

## Infinite Computations, Convergence, Formal Describability

Most traditional computability theory focuses on properties of halting programs. Given an MTM or EOM or GTM with halt instruction and , we write

 (1)

for  computes on 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 denote the input string or program read by TM T. Let denote T's finite output string after instructions. We say that and 's output stabilize and converge towards iff for each satisfying there exists a postive integer such that for all : and . Then we write
 (2)

Although each beginning or prefix of 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 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 is T-describable or T-computable iff there is a finite such that .

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

Definition 2.3 (Universal TMs)   Let denote a set of TMs. has a universal element if there is a TM such that for each there exists a constant string (the compiler) such that for all possible programs , if then .

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

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 denote a set of TMs with universal element . Some is C-describable or C-computable if it is -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 always converges if for all of its possible programs there is an such that .

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

Definition 2.7 (Approximability)   Let denote a real number, . is approximable by TM if there is a such that for each real there exists a such that

for all times . is approximable if there is at least one GTM as above.

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

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

Next: Formally Describable Functions Up: Preliminaries Previous: Turing Machines: Monotone TMs
Juergen Schmidhuber 2003-02-13