The "Almost All" Theory of Subrecursive Degrees is Decidable

Kurt Mehlhorn

Abstract

We use constructive measure theory to show the decidability of the ‘almost all’ theory of subrecursive degrees. The formulas of this theory are built up using the constant 0 standing for the minimum degree, the functions ∪, ∩ standing for the join and meet of two degrees respectively, the relation ≤ standing for the reducibility the logical connectives &, ┐, and the quantifier (for almost all a). An efficient decision procedure is described.
BibTeX
@inproceedings{mehlhorn1974almost,
  author = {Kurt Mehlhorn},
  title = {{The "Almost All" Theory of Subrecursive Degrees is Decidable}},
  booktitle = {ICALP},
  year = {1974},
  doi = {10.1007/3-540-06841-4\_70},
}

Loading related content...

Figure