Formally Describable Functions

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 $T(p) = infty$. 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 $B^{sharp}$, sometimes from $B^{sharp}$ to $B^{sharp}$.

Definition 2.8 (Encoding $B^*$)   Encode $x in B^*$ as a self-delimiting input $p(x)$ for an appropriate TM, using

$$l(p(x)) = l(x) + 2log l(x) + O(1)$$ (3)

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 $p(x)=1100110101101$.

Definition 2.9 (Recursive Functions)   A function $h: D_1 subset B^* rightarrow D_2 subset B^*$ is recursive if there is a TM $T$ using the encoding 2.8 such that for all $x in D_1: T(p(x)) = h(x)$.

Definition 2.10 (Describable Functions)   Let $T$ denote a TM using the encoding of Def. 2.8. A function $h: D_1 subset B^* rightarrow D_2 subset B^{sharp}$ is $T$-describable if for all $x in D_1: T(p(x)) leadsto h(x)$. Let $C$ denote a set of TMs using encoding 2.8, with universal element $U^C$. $h$ is C-describable or C-computable 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.

Compare functions in the arithmetic hierarchy [34] and the concept of $Delta^0_n$ describability, e.g., [30, p. 46-47].