Next: Formally Describable Functions
Up: Preliminaries
Previous: Turing Machines: Monotone TMs
Most traditional computability theory focuses on
properties of halting programs.
Given an MTM or EOM or GTM with halt instruction
and ,
we write
|
(1) |
for `` computes on and halts''.
Much of this paper, however, deals with programs
that never halt, and with TMs that do not need halt instructions.
Definition 2.1 (Convergence)
Let
denote
the input string or program read by TM T. Let
denote T's finite output
string after
instructions. We say that
and
's output
stabilize and
converge towards
iff for each
satisfying
there exists a postive integer
such that for all
:
and
.
Then we write
|
(2) |
Although each beginning or prefix of eventually becomes stable during the possibly
infinite computation, there need not be a halting program that computes
an upper bound of stabilization time, given any and prefix size.
Compare the concept of computability in the limit
[19,33,15] and [20,32].
Definition 2.2 (TM-Specific Individual Describability)
Given a TM T,
an
is
T-describable or
T-computable iff
there is a finite
such that
.
According to this definition, objects with infinite shortest descriptions on
are not -describable, reflecting the fact that we will never ever be able
to produce a complete -based description of such an object.
Definition 2.3 (Universal TMs)
Let
denote a set of TMs.
has a
universal element if there is a TM
such that for each
there exists a constant string
(the
compiler) such
that for all possible programs
, if
then
.
Definition 2.4 (M, E, G)
Let
denote the set of MTMs,
denote the set of EOMs,
denote the
set of GTMs.
all have universal elements, according to
the fundamental compiler theorem (for instance, a fixed compiler
can translate arbitrary LISP programs into equivalent FORTRAN programs).
Definition 2.5 (Individual Describability)
Let
denote a set
of TMs with universal element
. Some
is
C-describable or
C-computable if it is
-describable.
E-describable strings are called
computably enumerable (c.e.).
G-describable strings
are called
formally describable or simply
describable.
Definition 2.6 (Always converging TMs)
TM
always converges if for all of its possible
programs
there is an
such that
.
For example, MTMs and EOMs converge always. GTMs do not.
Definition 2.7 (Approximability)
Let
denote a real
number,
.
is
approximable by TM
if
there is a
such that for each real
there
exists a
such that
for all
times
.
is
approximable if there is at least
one GTM
as above.
Lemma 2.1
If
is approximable, then
is describable, and vice versa.
Henceforth we will exchangeably use the expressions
approximable, describable, computable in the limit.
Next: Formally Describable Functions
Up: Preliminaries
Previous: Turing Machines: Monotone TMs
Juergen Schmidhuber
2003-02-13