Alpha recursion theory: Difference between revisions

Revision as of 11:58, 25 January 2024

Revision as of 11:59, 25 January 2024

Line 40:

A computational interpretation of <math>\alpha</math>-recursion exists, using "<math>\alpha</math>-Turing machines" with a two-symbol tape of length <math>\alpha</math>, that at limit computation steps take the [[limit inferior]] of cell contents, state, and head position. For admissible <math>\alpha</math>, a set <math>A\subseteq\alpha</math> is <math>\alpha</math>-recursive iff it is computable by an <math>\alpha</math>-Turing machine, and <math>A</math> is <math>\alpha</math>-recursively-enumerable iff <math>A</math> is the range of a function computable by an <math>\alpha</math>-Turing machine. <ref>P. Koepke, B. Seyfferth, "[https://www.math.uni-bonn.de/people/koepke/Preprints/Ordinal_machines_and_admissible_recursion_theory.pdf Ordinal machines and admissible recursion theory]". Annals of Pure and Applied Logic vol. 160 (2009), pp.310--318.</ref>

A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible <math>\alpha</math>, the automorphisms of the <math>\alpha</math>-enumeration degrees embed into the automorphisms of the <math>\alpha</math>-enumeration degrees.<ref>D. (Natingga, ''Embedding Theorem for the automorphism group of the α-enumeration degrees'', (p.155), PhD thesis, 2019).</ref>

==Relationship to analysis==