Next: Complexity of Constructive Descriptions Up: Preliminaries Previous: Formally Describable Functions

## Weak Decidability and Convergence Problem

Traditionally, decidability of some problem class implies there is a halting algorithm that prints out the answer, given a problem from the class. We now relax the notion of decidability by allowing for infinite computations on EOMs or GTMs whose answers converge after finite yet possibly unpredictable time. Essentially, an answer needs to be correct for almost all the time, and may be incorrect for at most finitely many initial time steps (compare the concept of computability in the limit [20,19,33,15] and super-recursive algorithms [6,8]).

Definition 2.11 (Weak decidability)   Consider a characteristic function : if satisfies a certain property, and otherwise. The problem of deciding whether or not some satisfies that property is weakly decidable if is describable (compare Def. 2.10).

Example 2.1   Is a given string a halting program for a given MTM? The problem is not decidable in the traditional sense (no halting algorithm solves the general halting problem [43]), but weakly decidable and even E-decidable, by a trivial algorithm: print 0'' on first output square; simulate the MTM on work tapes and apply it to , once it halts after having read no more than bits print 1'' on first output square.

Example 2.2   It is weakly decidable whether a finite bitstring is a program for a given TM. Algorithm: print 0''; feed bitwise into the internally simulated TM whenever it requests a new input bit; once the TM has requested bits, print 1''; if it requests an additional bit, print 0''. After finite time the output will stabilize forever.

Example 2.3   It is weakly decidable whether number theory is consistent (contrast this with Gödel's famous negative result [18]).

Theorem 2.1 (Convergence Problem)   Given a GTM, it is not weakly decidable whether a finite bitstring is a converging program, or whether some of the output bits will fluctuate forever.

Proof. (Based on the standard diagonalization trick [11,18,43]; compare a related result for analytic TMs [12,21]). Let us write if there is a such that . Let us write if 's output fluctuates forever in response to (e.g., by flipping from 1 to zero and back forever). Let be an effective enumeration of all GTMs. Uniquely encode all pairs of finite strings in as finite strings . Suppose there were a GTM U such that (*): for all : if , and otherwise. Then one could construct a GTM with if , and otherwise. Let be the index of , then if , otherwise . By (*), however, if , and if . Contradiction.

Next: Complexity of Constructive Descriptions Up: Preliminaries Previous: Formally Describable Functions
Juergen Schmidhuber 2003-02-13