Next: Weak Decidability and Convergence
Up: Preliminaries
Previous: Infinite Computations, Convergence, Formal
Much of the traditional theory of computable functions focuses
on halting programs that map subsets of to subsets of .
The output of a program that does not halt is usually
regarded as undefined, which is occasionally expressed by
notation such as .
In this paper, however, we will not lump together
all the possible outputs of nonhalting programs
onto a single symbol ``undefined.'' Instead we will
consider mappings from subsets of to subsets
of , sometimes from
to .
Definition 2.8 (Encoding
)
Encode
as a selfdelimiting input
for an appropriate TM, using

(3) 
bits as follows: write
in binary notation,
insert a ``0'' after every ``0'' and a ``1'' after every ``1,''
append ``01'' to indicate the
end of the description of the size of the following string,
then append
.
For instance, gets encoded as
.
Definition 2.9 (Recursive Functions)
A function
is
recursive if there is a TM
using the encoding
2.8 such that
for all
.
Definition 2.10 (Describable Functions)
Let
denote a TM using the encoding of Def.
2.8.
A function
is
describable if
for all
.
Let
denote a set of TMs using encoding
2.8,
with universal element
.
is
Cdescribable
or
Ccomputable if it is
computable.
If the
above is universal
among the GTMs with such input encoding
(see Def.
2.3)
then
is
describable.
Compare functions in the arithmetic hierarchy [34]
and the concept of describability, e.g.,
[30, p. 4647].
Next: Weak Decidability and Convergence
Up: Preliminaries
Previous: Infinite Computations, Convergence, Formal
Juergen Schmidhuber
20030213