dbo:abstract
|
- 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:
* 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. (en)
|
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 6685 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
dcterms:subject
| |
rdfs:comment
|
- 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. (en)
|
rdfs:label
|
- Alpha recursion theory (en)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageRedirects
of | |
is dbo:wikiPageWikiLink
of | |
is foaf:primaryTopic
of | |