This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the k+1-r.e. numberings; all further reductions are obtained by (...) concatenating these reductions. (shrink)

We examine a definition of the mutual information of two reals proposed by Levin in [5]. The mutual information iswhereK is the prefix-free Kolmogorov complexity. A realAis said to have finite self-information ifI is finite. We give a construction for a perfect Π10class of reals with this property, which settles some open questions posed by Hirschfeldt and Weber. The construction produces a perfect set of reals withK≤+KA+f for any given Δ20fwith a particularly nice approximation and for a specific choice of (...) f it can also be used to produce a perfect Π10set of reals that are low for effective Hausdorff dimension and effective packing dimension. The construction can be further adapted to produce a single perfect set of reals that satisfyK≤+KA+f for allfin a ‘nice’ class of Δ20functions which includes all Δ20orders. (shrink)

Less discussed than Hume’s skepticism about what grounds there could be for projecting empirical hypotheses is his concern with a skeptical regress that he thought threatened to extinguish any belief when we reflect that our reasoning is not perfect. The root of the problem is the fact that a reflection about our reasoning is itself a piece of reasoning. If each reflection is negative and undermining, does that not give us a diminution of our original belief to nothing? It requires (...) much attention to detail, we argue, to determine whether or not there is a skeptical problem in this neighborhood. Consider that if we subsequently doubt a doubt we had about our reasoning, that would suggest a restoration of some of the force of our original belief. We would then have instead of runaway skepticism an alternating sequence of pieces of skeptical reasoning that cancel each others’ effects on our justification in the original proposition, at least to some degree. We will argue that the outcome of the sequence of reflections Hume is imagining depends on information about a given case that is not known a priori. We conclude this from the fact that under three precise, explanatory, and viable contemporary reconstructions of what this kind of reasoning about reasoning could be like and how it has the potential to affect our original beliefs, a belief-extinguishing regress is not automatic or necessary. (shrink)

The Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A isK-trivial if its initial segments have the lowest possible complexity and A is low forKif using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all${\rm{\Delta }}_2^0$orders, and call the (...) new notions${\rm{\Delta }}_2^0$-bounded K-trivialand${\rm{\Delta }}_2^0$-bounded low for K. Several of the ‘nice’ properties ofK-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the${\rm{\Delta }}_2^0$-boundedK-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namelyinfinitely-often K-trivialityandweak lowness for K. We show that${\rm{\Delta }}_2^0$-boundedK-trivial implies infinitely-oftenK-trivial, but no implication holds between${\rm{\Delta }}_2^0$-bounded low forKand weakly low forK. (shrink)