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 $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.1   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 [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 $p$, once it halts after having read no more than $l(p)$ bits print ``1'' on first output square.

Example 2.2   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.

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