The "Almost All" Theory of Subrecursive Degrees is Decidable
We use constructive measure theory to show the decidability pf 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 $\cup,\cap$ standing for the join and meet of two degrees respectively, the relation $\leq$ standing for the reducibility-ordering, the logical connectives "ampersand", $\neg$ and the quantifier (almost $\forall$ a). An efficient decision procedure is described.
computer science; technical report
Previously Published As