Alpha Recursion Theory

Alpha Recursion Theory

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible ordinal is closed under functions. Admissible ordinals are models of Kripke–Platek set theory. In what follows is considered to be fixed.

The objects of study in recursion are subsets of . A is said to be recursively enumerable if it is definable over . A is recursive if both A and (its complement in ) are recursively enumerable.

Members of are called finite and play a similar role to the finite numbers in classical recursion theory.

We say R is a reduction procedure if it is recursively enumerable and every member of R is of the form where H, J, K are all α-finite.

A is said to be α-recusive in B if there exist reduction procedures such that:

If A is recursive in B this is written . By this definition A is recursive in (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being .

We say A is regular if or in other words if every initial portion of A is α-finite.

Read more about Alpha Recursion Theory:  Results in Recursion

Famous quotes containing the words alpha and/or theory:

    Imagination is a valuable asset in business and she has a sister, Understanding, who also serves. Together they make a splendid team and business problems dissolve and the impossible is accomplished by their ministrations.... Imagination concerning the world’s wants and the individual’s needs should be the Alpha and Omega of self-education.
    Alice Foote MacDougall (1867–1945)

    every subjective phenomenon is essentially connected with a single point of view, and it seems inevitable that an objective, physical theory will abandon that point of view.
    Thomas Nagel (b. 1938)