Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Computable categoricity versus relative computable categoricity

100%

Downey R., Kach A., Lempp S., Turetsky D.

Fundamenta Mathematicae

2013

tom 221

nr 2

129-159

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 categoricity and relative computable categoricity and its relativizations.

Asymptotic density, computable traceability, and 1-randomness

88%

Andrews U., Cai M., Diamondstone D., Jockusch C., Lempp S.

Fundamenta Mathematicae

2016

tom 234

nr 1

41-53

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.

Ograniczanie wyników

2 Fundamenta Mathematicae

2 Lempp S.

1 Andrews U.

1 Cai M.

1 Diamondstone D.

1 Downey R.

1 Jockusch C.

1 Kach A.

1 Turetsky D.

1 2016

1 2013

Wyniki wyszukiwania

Computable categoricity versus relative computable categoricity

Asymptotic density, computable traceability, and 1-randomness