Alpha recursion theory
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible set is closed under functions, where denotes a rank of Godel's constructible hierarchy. is an admissible ordinal if is a model of Kripke–Platek set theory. In what follows is considered to be fixed. The objects of study in recursion are subsets of . These sets are said to have some properties: There are also some similar definitions for functions mapping to : * The functions -definable in play a role similar to those of the primitive recursive functions.
- Comment
- enIn recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible set is closed under functions, where denotes a rank of Godel's constructible hierarchy. is an admissible ordinal if is a model of Kripke–Platek set theory. In what follows is considered to be fixed. The objects of study in recursion are subsets of . These sets are said to have some properties: There are also some similar definitions for functions mapping to : * The functions -definable in play a role similar to those of the primitive recursive functions.
- Has abstract
- enIn recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible set is closed under functions, where denotes a rank of Godel's constructible hierarchy. is an admissible ordinal if is a model of Kripke–Platek set theory. In what follows is considered to be fixed. The objects of study in recursion are subsets of . These sets are said to have some properties: * A set is said to be -recursively-enumerable if it is definable over , possibly with parameters from in the definition. * A is -recursive if both A and (its relative complement in ) are -recursively-enumerable. It's of note that -recursive sets are members of by definition of . * Members of are called -finite and play a similar role to the finite numbers in classical recursion theory. There are also some similar definitions for functions mapping to : * A function mapping to is -recursively-enumerable iff its graph is -definable in . * A function mapping to is -recursive iff its graph is -definable in . * Additionally, a function mapping to is -arithmetical iff there exists some such that the function's graph is -definable in . Additional connections between recursion theory and α recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them: * The functions -definable in play a role similar to those of the primitive recursive functions. 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 α-recursive 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.
- Is primary topic of
- Alpha recursion theory
- Label
- enAlpha recursion theory
- Link from a Wikipage to an external page
- projecteuclid.org/euclid.bams/1183541465
- projecteuclid.org/euclid.pl/1235422631
- core.ac.uk/download/pdf/30905237.pdf
- Link from a Wikipage to another Wikipage
- Admissible ordinal
- Category:Computability theory
- Constructible hierarchy
- Empty set
- Kripke–Platek set theory
- Levy hierarchy
- Primitive recursion
- Recursion theory
- Relative complement
- Second-order arithmetic
- SameAs
- 4PoPi
- m.02vls68
- Q4735170
- Subject
- Category:Computability theory
- WasDerivedFrom
- Alpha recursion theory?oldid=1122612606&ns=0
- WikiPageLength
- 6685
- Wikipage page ID
- 12008116
- Wikipage revision ID
- 1122612606