Much of the traditional theory of computable functions focuses
on halting programs that map subsets of B* to subsets of B*.
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 B* to subsets
Definition 2.8 (Encoding tex2html_wrap_inline$B^*$)
as a self-delimiting input p(x)
for an appropriate TM, using
l(p(x)) = l(x) + 2logl(x) + O(1)
bits as follows: write l(x) 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 x.
For instance, x=01101 gets encoded as
Definition 2.9 (Recursive Functions)
recursive if there is a TM T using the encoding 2.8 such that
Definition 2.10 (Describable Functions)
Let T denote a TM using the encoding of Def. 2.8.
Let C denote a set of TMs using encoding 2.8,
with universal element UC. h is C-describable
or C-computable if it is UC-computable.
If the T above is universal
among the GTMs with such input encoding
(see Def. 2.3)
then h is describable.
Compare functions in the arithmetic hierarchy [#!Rogers:67!#]
and the concept of
[#!LiVitanyi:97!#, p. 46-47].