Turing complexity of the ordinals

DOI10.1016/0020-0190(86)90130-4zbMath0626.03032OpenAlexW2030306339MaRDI QIDQ580332

Patrick Dehornoy

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90130-4

zbMATH Keywords

Turing machinesCountable ordinalsrecursive ordinal

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items

\(\Pi^ 1_ 1\)-complete families of elementary sequences, Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n)), Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization, A coding of the countable linear orderings

Cites Work

• Unnamed Item
• Unnamed Item