A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
From MaRDI portal
Publication:3710515
DOI10.2307/2274189zbMath0585.03015OpenAlexW2002729262MaRDI QIDQ3710515
Publication date: 1984
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2274189
counterexamplesorder typeseffective translationinfinite injury priority argumentinfinite recursive linearly ordered setinfinite subsequences
Nonstandard models of arithmetic (03H15) Theory of numerations, effectively presented structures (03D45)
Related Items
Finite condensations of recursive linear orders ⋮ Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n)) ⋮ Computability on linear orderings enriched with predicates ⋮ Cuts of linear orders ⋮ Recursive Linear Orders with Incomplete Successivities ⋮ Depth zero Boolean algebras ⋮ Codings on linear orders and algorithmic independence of natural relations ⋮ Every Low Boolean Algebra is Isomorphic to a Recursive One ⋮ Computable presentability of countable linear orders ⋮ Intrinsic bounds on complexity and definability at limit levels ⋮ On computable self-embeddings of computable linear orderings