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.
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.
Mathematics 472 (Statistical Inference), University of Hawaii at Manoa, Spring 2009.
This project concerns the distribution of the nearest walk of length \(n\) to a randomly chosen walk of length \(m>n\),
where the walks have step size \(1/n\) on the \(x\)-axis and \(1/\sqrt n\) on the \(y\)-axis.
It is well known that the distribution of such walks converges to Brownian motion.
Two of the groups in the class found that strings of the form \(1^a0^b\) and \(0^a 1^b\) were the least likely nearest walks, whereas strings of the form \(0101\ldots\) or \(1010\ldots\) were the most likely. Strings of the form \(000\ldots\) or \(111\ldots\) were the second least likely.
math overflow questions:
I work in mathematical logic, computability theory and algorithmic randomness.
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.
Some open problems are available in a Banff research station archive file.