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* = *A*_{y}, then
if
,
otherwise
.
By **(*)**, however,
if
,
and
if
.
Contradiction.

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