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
of
,
sometimes from
to
.
Definition 2.8 (Encoding tex2html_wrap_inline$B^*$)
Encode
as a selfdelimiting input
p(
x)
for an appropriate TM, using
l(p(x)) = l(x) + 2log l(x) + O(1)

(5) 
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.
Definition 2.10 (Describable Functions)
Let
T denote a TM using the encoding of Def.
2.8.
A function
is
Tdescribable if
for all
.
Let
C denote a set of TMs using encoding
2.8,
with universal element
U^{C}.
h is
Cdescribable
or
Ccomputable if it is
U^{C}computable.
If the
T above is universal
among the GTMs with such input encoding
(see Def.
2.3)
then
h is
describable.