|
Alpha Recursion Theory
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals \alpha. An admissible set is closed under \Sigma_1(L_\alpha) functions, where L_\xi denotes a rank of Godel's constructible hierarchy. \alpha is an admissible ordinal if L_ is a model of Kripke–Platek set theory. In what follows \alpha is considered to be fixed. Definitions The objects of study in \alpha recursion are subsets of \alpha. These sets are said to have some properties: *A set A\subseteq\alpha is said to be \alpha-recursively-enumerable if it is \Sigma_1 definable over L_\alpha, possibly with parameters from L_\alpha in the definition. *A is \alpha-recursive if both A and \alpha \setminus A (its relative complement in \alpha) are \alpha-recursively-enumerable. It's of note that \alpha-recursive sets are members of L_ by definition of L. *Members of L_\alpha are called \alpha-finite and play a similar role to the finite numbers in classical recursion th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Recursion Theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definable set, definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: * What does it mean for a function (mathematics), function on the natural numbers to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of computational complexity theory ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |