Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Asymptotic density, computable traceability, and 1-randomness

Uri AndrewsMingzhong CaiDavid DiamondstoneCarl JockuschSteffen Lempp — 2016

Fundamenta Mathematicae

Let r ∈ [0,1]. A set A ⊆ ω is said to be coarsely computable at density r if there is a computable function f such that {n | f(n) = A(n)} has lower density at least r. Our main results are that A is coarsely computable at density 1/2 if A is computably traceable or truth-table reducible to a 1-random set. In the other direction, we show that if a degree a is hyperimmune or PA, then there is an a-computable set which is not coarsely computable at any positive density.

Computable categoricity versus relative computable categoricity

Rodney G. DowneyAsher M. KachSteffen LemppDaniel D. Turetsky — 2013

Fundamenta Mathematicae

We study the notion of computable categoricity of computable structures, comparing it especially to the notion of relative computable categoricity and its relativizations. We show that every 1 decidable computably categorical structure is relatively Δ⁰₂ categorical. We study the complexity of various index sets associated with computable categoricity and relative computable categoricity. We also introduce and study a variation of relative computable categoricity, comparing it to both computable...

Page 1

Download Results (CSV)