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!#]).
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 if there is a such that . Let us write if T's output fluctuates forever in response to x (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 (x,y) in as finite strings . Suppose there were a GTM U such that (*): for all : if , and otherwise. Then one could construct a GTM T with if , and otherwise. Let y be the index of T = Ay, then if , otherwise . By (*), however, if , and if . Contradiction.