Formally Describable Functions
Next: Weak Decidability and Convergence Up: Preliminaries Previous: Infinite Computations, Convergence, Formal

## 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 . 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 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 is recursive if there is a TM T using the encoding 2.8 such that for all .

Definition 2.10 (Describable Functions)   Let T denote a TM using the encoding of Def. 2.8. A function is T-describable if for all . 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 -describability, e.g., [#!LiVitanyi:97!#, p. 46-47].

Next: Weak Decidability and Convergence Up: Preliminaries Previous: Infinite Computations, Convergence, Formal
Juergen Schmidhuber
2001-01-09

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