The Computability Menagerie houses animals of varying degrees of non-computability. The project started during my Marie Curie fellowship in Heidelberg, where I was working on a huge diagram of downward closed classes of Turing degrees, using JFig.
Mushfeq Khan and Joe Miller have written a web app version of the menagerie.
Related research on André Nies’ home page:
Logic Blog
Tamer (computable) creatures are on display at the Complexity Zoo.
Kolmogorov complexity and strong approximation of Brownian motion
(with Tamás Szabados). Proceedings of the American Mathematical Society 139 (2011) no. 9, 3307—3316.
In this email-collaboration paper we improved a bound from Asarin (Kolmogorov’s PhD student) and Pokrovskii’s paper on Kolmogorov complexity and Brownian motion.
Kolmogorov complexity and the recursion theorem (with Wolfgang Merkle and Frank Stephan). Transactions of the American Mathematical Society363 (2011) no. 10, 5465—5480.
arXiv:0901.3933. Preliminary version in STACS 2006, Lecture Notes in Computer Science,
vol. 3884, Springer, Berlin, 2006, pp. 149—161.
The groundwork for this paper was laid in Berkeley in 2004 while Merkle and I were both stopping by there. The paper fits in a long line of results saying “DNR is equivalent to…”, in this case to computing a real whose initial segment complexity is sufficiently high.
A strong law of computationally weak subsets
Journal of Mathematical Logic 11 (2011) no. 1, 1—10.
DOI: 10.1142/S0219061311000980
Electronic Colloquium on Computational Complexity, Report No. 150 (2010).
This paper establishes a new statistical law, namely that for each random sequence
$$0111011101101101101\ldots$$
it is possible to replace some of the 1s by 0s (in other words, form a subset of 1s) in such a way that no random sequence can be recovered by computational means.
To illustrate, imagine that the new sequence looks like
$$0111010101101000101\ldots$$
Technically the result is that each 2-random set has an infinite subset computing no 1-random set. It is perhaps the main result obtained under Prof. Kjos-Hanssen’s grant NSF DMS-0901020 (2009-2013).
Joseph S. Miller at U. of Wisconsin has established a strengthening of this result replacing 2-random by 1-random, but that result is so far unpublished.
Dr. Bjørn Kjos-Hanssen is a professor at the University of Hawai‘i at Manoa in the Department of Mathematics. His research deals with the abstract theory of computation, computability, randomness and compression algorithms.
Kjos-Hanssen is the author of more than 20 papers in journals including the prestigious Mathematical Research Letters and Transactions of the American Mathematical Society, and has a PhD from UC Berkeley in the subject Logic and the Methodology of Science.
Quinn Culver (Master of Arts, 2010). Thesis: Polynomial-clone reducibility. After finishing this thesis under my direction, he moved on to University of Notre Dame to pursue a PhD.
Superhighness
(with André Nies). Notre Dame Journal of Formal Logic 50 (2009), no. 4, 445—452.
This paper written on Maui has since been superseded in at least two ways.
Lattice initial segments of the hyperdegrees
(with Richard A. Shore). Journal of Symbolic Logic 75 (2010), no. 1, 103—130.
I was a postdoc with Shore during the academic year 2006-2007 at Cornell, and this paper was the result of our joint work there. It concerns hyperarithmetical reducibility and its induced partial ordering of the reals.
Higher Kurtz randomness
(with André Nies, Frank Stephan, and Liang Yu). Annals of Pure and Applied Logic 161 (2010), no. 10, 1280—1290.
I visited Liang Yu at Nanjing University, China in 2008 and 2009. The collaboration for this paper however was later done by email plus a strategy meeting in Marseille in 2009.