โ Scribed by Sebastiaan A. Terwijn; Leen Torenvliet
No coin nor oath required. For personal study only.
This yields the same notion of measure 0 set as considered before by Martin-Lof, Schnorr, and others. We prove that the class of sets constructible by r.e.-constructors, a direct analogue of the classes Lutz devised his resource bounded measures for in [lo], is not equal to RE, the class of r.e. sets, and we locate this class exactly in terms of the common recursion-theoretic reducibilities below h'. We note that the class of sets that bounded truth-table reduce t o K has r.e.-measure 0 , and show that this cannot be improved to truth-table. For Az-measure the borderline between measure zero and measure nanzero lies between weak truth-table reducibility and Turing reducibility t o h'. It follows that there exists a Martin-Lof random set that is tt-reducible to K , and that no such set is btt-reducible to K . In fact, by a result of Kautz, a much more general result holds.
๐ SIMILAR VOLUMES