In algorithmic randomness we try to determine what it takes to produce randomness, and what you can do with it once you have it.
Logic and computability deal with the borders between the complete and the incomplete, the decidable and the undecidable, the computable and the non-computable. A fundamental result in the area is Gödel’s 1931 incompleteness theorem, which is a precise version of the following sentiment of Ishmail in Moby Dick.
I promise nothing complete; because any human thing supposed to be complete, must for that very reason infallibly be faulty.
Laurent Bienvenu and Paul Shafer discovered an apparent error in the proof of Lemma 4.6. There it is stated that A wtt-reduces to B; however, it seems that the reduction of A to B also requires oracle access to f. Corollary 4.7 also seems false (take f to be a ML random of hyperimmune-free degree, and A=f; then A is complex but not f-complex).
Self-embeddings of computable trees (with Stephen Binns, Manuel Lerman, Jim Schmerl, and Reed Solomon). Notre Dame Journal of Formal Logic49 (2008), no. 1, 1—37.
I was probably the least-involved of the five authors of this paper, which was written in 2005-2006 at UConn.
The strength of some combinatorial principles related to Ramsey’s theorem
(with Denis R. Hirschfeldt, Carl G. Jockusch, Steffen Lempp, and Theodore A. Slaman.) Computational Prospects of Infinity. Part II: Presented Talks, Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore, vol. 15, World Scientific Publishing, Hackensack, NJ, 2008, pp. 143—162.
This paper established that Stable Ramsey’s Theorem for pairs implies DNR, which is a weak form of WKL.
It was later shown by Liu in 2011 that Ramsey’s theorem for pairs does not imply WKL (which is what we really wanted to know!).
This paper was written while all authors were participating in the Computational Prospects of Infinity workshop in Singapore in 2005.
This paper was concerned with the difference between highness and almost everywhere domination in the Turing degrees. This was taken further in later papers.
In this paper the idea of mixed lowness notions seems to have been born (?). This idea actually occurred to me while unlocking my bicycle in Heidelberg.
Comparing DNR and WWKL (with Klaus Ambos-Spies, Steffen Lempp, and Theodore A. Slaman).
Journal of Symbolic Logic69 (2004), no. 4, 1089—1104.
This paper (which is mentioned in Wikipedia under Reverse Mathematics) separated DNR from WWKL. It was mostly written while all four authors were in Heidelberg during 2002-2003.
Professor of Mathematics, University of Hawaii at Manoa