wikiwand.com

Alpha recursion theory - Wikiwand

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals {\displaystyle \alpha }. An admissible set is closed under {\displaystyle \Sigma _{1}(L_{\alpha })} functions, where {\displaystyle L_{\xi }} denotes a rank of Godel's constructible hierarchy. {\displaystyle \alpha } is an admissible ordinal if {\displaystyle L_{\alpha }} is a model of Kripke–Platek set theory. In what follows {\displaystyle \alpha } is considered to be fixed.

The objects of study in {\displaystyle \alpha } recursion are subsets of {\displaystyle \alpha }. These sets are said to have some properties:

There are also some similar definitions for functions mapping {\displaystyle \alpha } to {\displaystyle \alpha }:[3]

Additional connections between recursion theory and α recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them:

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

A is said to be α-recursive in B if there exist {\displaystyle R_{0},R_{1}} reduction procedures such that:

{\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{0}\wedge H\subseteq B\wedge J\subseteq \alpha /B],}
{\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{1}\wedge H\subseteq B\wedge J\subseteq \alpha /B].}

If A is recursive in B this is written {\displaystyle \scriptstyle A\leq _{\alpha }B}. By this definition A is recursive in {\displaystyle \scriptstyle \varnothing } (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being {\displaystyle \Sigma _{1}(L_{\alpha }[B])}.

We say A is regular if {\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }} or in other words if every initial portion of A is α-finite.

Shore's splitting theorem: Let A be {\displaystyle \alpha } recursively enumerable and regular. There exist {\displaystyle \alpha } recursively enumerable {\displaystyle B_{0},B_{1}} such that {\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}

Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that {\displaystyle \scriptstyle A<_{\alpha }C} then there exists a regular α-recursively enumerable set B such that {\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}.

Barwise has proved that the sets {\displaystyle \Sigma _{1}}-definable on {\displaystyle L_{\alpha ^{+}}} are exactly the sets {\displaystyle \Pi _{1}^{1}}-definable on {\displaystyle L_{\alpha }}, where {\displaystyle \alpha ^{+}} denotes the next admissible ordinal above {\displaystyle \alpha }, and {\displaystyle \Sigma } is from the Levy hierarchy.[5]

There is a generalization of limit computability to partial {\displaystyle \alpha \to \alpha } functions.[6]

A computational interpretation of {\displaystyle \alpha }-recursion exists, using "{\displaystyle \alpha }-Turing machines" with a two-symbol tape of length {\displaystyle \alpha }, that at limit computation steps take the limit inferior of cell contents, state, and head position. For admissible {\displaystyle \alpha }, a set {\displaystyle A\subseteq \alpha } is {\displaystyle \alpha }-recursive iff it is computable by an {\displaystyle \alpha }-Turing machine, and {\displaystyle A} is {\displaystyle \alpha }-recursively-enumerable iff {\displaystyle A} is the range of a function computable by an {\displaystyle \alpha }-Turing machine. [7]

A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible {\displaystyle \alpha }, the automorphisms of the {\displaystyle \alpha }-enumeration degrees embed into the automorphisms of the {\displaystyle \alpha }-enumeration degrees.[8]

Some results in {\displaystyle \alpha }-recursion can be translated into similar results about second-order arithmetic. This is because of the relationship {\displaystyle L} has with the ramified analytic hierarchy, an analog of {\displaystyle L} for the language of second-order arithmetic, that consists of sets of integers.[9]

In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on {\displaystyle L_{\omega }={\textrm {HF}}}, the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a {\displaystyle \Sigma _{1}^{0}} formula iff it's {\displaystyle \Sigma _{1}}-definable on {\displaystyle L_{\omega }}, where {\displaystyle \Sigma _{1}} is a level of the Levy hierarchy.[10] More generally, definability of a subset of ω over HF with a {\displaystyle \Sigma _{n}} formula coincides with its arithmetical definability using a {\displaystyle \Sigma _{n}^{0}} formula.[11]

Loading related searches...