Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets

&
Annals of Pure and Applied Logic 141 (3):437-441 (2006)
  Copy   BIBTEX

Abstract

Let μ be a universal lower enumerable semi-measure . Any computable upper bound for μ can be effectively separated from zero with a constant . Computable positive lower bounds for μ can be nontrivial and allow one to construct natural examples of hypersimple sets

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2005.12.007

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,069

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Turing degrees of hypersimple relations on computable structures.Valentina S. Harizanov - 2003 - Annals of Pure and Applied Logic 121 (2-3):209-226.
Effectively closed sets of measures and randomness.Jan Reimann - 2008 - Annals of Pure and Applied Logic 156 (1):170-182.
The complexity of central series in nilpotent computable groups.Barbara F. Csima & Reed Solomon - 2011 - Annals of Pure and Applied Logic 162 (8):667-678.
A uniform method for proving lower bounds on the computational complexity of logical theories.Kevin J. Compton & C. Ward Henson - 1990 - Annals of Pure and Applied Logic 48 (1):1.
Natural factors of the Muchnik lattice capturing IPC.Rutger Kuyper - 2013 - Annals of Pure and Applied Logic 164 (10):1025-1036.
Difference sets and computability theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
The complexity of the disjunction and existential properties in intuitionistic logic.Sam Buss & Grigori Mints - 1999 - Annals of Pure and Applied Logic 99 (1-3):93-104.
Local stability of ergodic averages.Jeremy Avigad - unknown
Hypersimplicity and semicomputability in the weak truth table degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
On the impossibility of explicit upper bounds on lengths of some provably finite algorithms in computable analysis.Andre Scedrov - 1986 - Annals of Pure and Applied Logic 32:291-297.

Analytics

Added to PP
2013-12-31

Downloads
25 (#654,431)

6 months
12 (#242,953)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Add more references