An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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.

Property Value
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
  • 12008116 (xsd:integer)
dbo:wikiPageLength
  • 6685 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1122612606 (xsd:integer)
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
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License