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 computability in the limit [#!Greg:57!#,#!Gold:65!#,#!Putnam:65!#,#!Freyvald:74!#] and super-recursive algorithms [#!Burgin:83!#,#!Burgin:91!#]).

Definition 2.11 (Weak decidability) Consider a characteristic function $h: D_1 \subset B^* \rightarrow B$ : h(x)=1 if x satisfies a certain property, and h(x)=0 otherwise. The problem of deciding whether or not some $x \in D_1$ satisfies that property is weakly decidable if h(x) is describable (compare Def. 2.10).

Example 2.2 Is a given string $p \in B^*$ a halting program for a given MTM? The problem is not decidable in the traditional sense (no halting algorithm solves the general halting problem [#!Turing:36!#]), 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 p, once it halts after having read no more than l(p) bits print ``1'' on first output square.

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

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. A proof conceptually quite similar to the one below was given by Hotz, Vierke and Schieffer [#!Hotz:95!#] in the context of analytic TMs [#!Hotz:99!#] derived from R-Machines [#!Blum:89!#] (the alphabet of analytic TMs is real-valued instead of binary). Version 1.0 of this paper [#!Schmidhuber:00version1!#] was written without awareness of this work. Nevertheless, the proof in Version 1.0 is repeated here because it does serve illustrative purposes.

In a straightforward manner we adapt Turing's proof of the undecidability of the MTM halting problem [#!Turing:36!#], a reformulation of Gödel's celebrated result [#!Goedel:31!#], using the diagonalization trick whose roots date back to Cantor's proof that one cannot count the real numbers [#!Cantor:1874!#]. Let us write $T(x) \downarrow$ if there is a $z \in B^{\sharp}$ such that $T(x) \leadsto z$ . Let us write $T(x) \updownarrow$ if T's output fluctuates forever in response to x (e.g., by flipping from 1 to zero and back forever). Let $A_1, A_2, \ldots$ be an effective enumeration of all GTMs. Uniquely encode all pairs of finite strings (x,y) in $B^* \times B^*$ as finite strings $code(x,y) \in B^*$ . Suppose there were a GTM U such that (*): for all $x,y \in B^*$ : $U(code(x,y)) \leadsto 1$ if $A_x(y) \downarrow$ , and $U(code(x,y)) \leadsto 0$ otherwise. Then one could construct a GTM T with $T(x) \leadsto 1$ if $U(code(x,x)) \leadsto 0$ , and $T(x) \updownarrow$ otherwise. Let y be the index of T = A_y, then $A_y(y) \downarrow$ if $U(code(y,y)) \leadsto 0$ , otherwise $A_y(y) \updownarrow$ . By (*), however, $U(code(y,y)) \leadsto 1$ if $A_y(y) \downarrow$ , and $U(code(y,y)) \leadsto 0$ if $A_y(y) \updownarrow$ . Contradiction. $\Box$