-
Called degrees. Post was particularly interested in computability from sets which are par-tially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer. These sets are called (recursively) enu-merable, as are their degrees. He showed [20] that the enumerable degrees (review)Bulletin of Symbolic Logic 1 (2). 1995.
-
174On recursion theory in I∑Journal of Symbolic Logic 54 (2). 1989.It is shown that the low basis theorem is meaningful and provable in I∑ 1 and that the priority-free solution to Post's problem formalizes in this theory
-
96Demuth’s path to randomnessBulletin of Symbolic Logic 21 (3): 270-305. 2015.Osvald Demuth studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.In this paper, we trace the path that took Demuth from his constructivist roots to …Read more
-
61On relative randomnessAnnals of Pure and Applied Logic 63 (1): 61-67. 1993.Kuera, A., On relative randomness, Annals of Pure and Applied Logic 63 61–67. It is the aim of the paper to answer a question raised by M. van Lambalgen and D. Zambella whether there can be a nonrecursive set A having the property that there is a set B such that B is 1-random relative to A and simultaneously A is recursive in B. We give apositive answer to this question as well as further information about relative randomness
-
97Demuth randomness and computational complexityAnnals of Pure and Applied Logic 162 (7): 504-513. 2011.Demuth tests generalize Martin-Löf tests in that one can exchange the m-th component a computably bounded number of times. A set fails a Demuth test if Z is in infinitely many final versions of the Gm. If we only allow Demuth tests such that GmGm+1 for each m, we have weak Demuth randomness.We show that a weakly Demuth random set can be high and , yet not superhigh. Next, any c.e. set Turing below a Demuth random set is strongly jump-traceable.We also prove a basis theorem for non-empty classes …Read more
-
133Lowness for the class of random setsJournal of Symbolic Logic 64 (4): 1396-1402. 1999.A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RAND A
-
155Low upper bounds of idealsJournal of Symbolic Logic 74 (2): 517-534. 2009.We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound
-
95Computing k-trivial sets by incomplete random setsBulletin of Symbolic Logic 20 (1): 80-90. 2014.EveryK-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.
