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 to subsets of . 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 to subsets of , sometimes from to .

Definition 2.8 (Encoding )   Encode as a self-delimiting input for an appropriate TM, using
 (3)

bits as follows: write 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 .

For instance, gets encoded as .

Definition 2.9 (Recursive Functions)   A function is recursive if there is a TM using the encoding 2.8 such that for all .

Definition 2.10 (Describable Functions)   Let denote a TM using the encoding of Def. 2.8. A function is -describable if for all . Let denote a set of TMs using encoding 2.8, with universal element . is C-describable or C-computable if it is -computable. If the above is universal among the GTMs with such input encoding (see Def. 2.3) then is describable.

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

Next: Weak Decidability and Convergence Up: Preliminaries Previous: Infinite Computations, Convergence, Formal
Juergen Schmidhuber 2003-02-13