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 tex2html_wrap_inline$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) (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.

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 [#!Rogers:67!#] and the concept of $\Delta^0_n$-describability, e.g., [#!LiVitanyi:97!#, p. 46-47].

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI