Infinite Computations, Convergence, Formal Describability    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 T with halt instruction and , 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 denote the input string or program read by TM T. Let Tt(p) denote T's finite output string after t instructions. We say that p and p's output stabilize and converge towards iff for each n satisfying there exists a postive integer tn such that for all : Tt(p)n = xn and . Then we write (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 is T-describable or T-computable iff there is a finite such that .

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 such that for each there exists a constant string (the compiler) such that for all possible programs p, if then .

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 UC. Some is C-describable or C-computable if it is UC-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 there is an such that .

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

Definition 2.7 (Approximability)   Let 0.x denote a real number, . 0.x is approximable by TM T if there is a such that for each real there exists a t0 such that for all times . 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.    Next: Formally Describable Functions Up: Preliminaries Previous: Turing Machines: Monotone TMs
Juergen Schmidhuber
2001-01-09

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