Order-computable sets

DOI10.1305/NDJFL/1187031407MaRDI QIDQ2469429zbMATH OpenOpenAlexFDO

Authors Denis R. Hirschfeldt, Sergei Podzorov, Russell Miller

Publication date 5 February 2008

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1187031407

zbMATH Keywords

computable ordercomputable structurecomputably enumerable setErshov's hierarchylimit computable setorder-computable set

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45)

Review text

A set \(A\subseteq\omega\) is called order-computable if the structure \(\langle\omega;<,A\rangle\) has a computable copy. The authors study general properties of order-computable sets, mostly the relationship of this property with Turing degrees. The most impressive result is the fact that there exist computably isomorphic c.e. sets one of which is order-computable and the other is not. Some open questions are formulated.

Recommendations

• On initial segments of computable linear orders
• Weak presentations of computable partial orderings
• Relative complexity for computable presentations of the conventional linear order on the set of naturals
• The Settling Time Reducibility Ordering and  Formula Sets
• Degree spectra of unary relations on \langle \omega, \leq \rangle

Cited in

(21)

• Weak presentations of computable ordered semigroups
• Effectively categorical abelian groups
• Orders of indescribable sets
• Weak presentations of computable partial orderings
• Limitwise monotonic sequences and degree spectra of structures
• Iterated effective embeddings of abelian p-groups
• On limitwise monotonicity and maximal block functions
• The computability path ordering
• scientific article; zbMATH DE number 3851063 (Why is no real title available?)
• The Settling Time Reducibility Ordering and  Formula Sets
• scientific article; zbMATH DE number 1303201 (Why is no real title available?)
• Orders on magmas and computability theory
• Examples of semicomputable sets of real and complex numbers
• Limitwise monotonic functions, sets, and degrees on computable domains
• COMPUTABILITY AND UNCOUNTABLE LINEAR ORDERS II: DEGREE SPECTRA
• Limitwise monotonic sets of reals
• Metric structures and probabilistic computation
• The settling-time reducibility ordering
• Comparing C.E. Sets Based on Their Settling Times
• η-representation of sets and degrees
• Computable shuffle sums of ordinals

This page was built for publication: Order-computable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2469429)