Joseph S. Miller
Office: 521 Van Vleck
Email: ude.csiw.htam@rellimj
Fax: (608) 263-8891
University of Wisconsin–Madison
Department of Mathematics
480 Lincoln Drive
Madison, WI 53706
The Computability Menagerie
The menagerie is a dynamic diagram of (downward closed) classes of Turing degrees. It is easy to use; just follow the link below and explore.

Between 2002 and 2003, Bjørn Kjos-Hanssen put together a remarkable diagram of classes of Turing degrees. His diagram is available below. It was constructed by hand in jfig (a graphics program written in Java and based on xfig) and contains over a hundred classes. Wanting to make Bjørn's diagram easier to use and easier to modify, I put together a database of facts about classes of Turing degrees and wrote a command-line program to process the database and produce a diagram. The static diagram generated by my program was still difficult to use, so Mushfeq Khan created the menagerie web app, making it easy to explore the diagram and quickly get the information you need. Bjørn's diagram. The computability menagerie is a direct descendent of Bjørn Kjos-Hanssen's original diagram.
  • The original file was in the FIG image format, which can be viewed with xfig or jfig.
  • There is also a PDF of Bjørn's diagram.
  • Bjørn converted most of his diagram into a database that works with the computability menagerie application.
    It has no justifications, few non-implications, and is missing a lot of information about the sizes of classes. On the other hand, it has 106 classes, many more than the current database.
  • This is a PNG of the diagram generated from Bjørn's database (with measure/dimension coloring and no unresolved implications).
The Reverse Mathematics Zoo. Damir Dzhafarov repurposed—or more accurately, rewrote—the command line version of the menagerie application and put together a database of weak principles in reverse mathematics. His program, database, and the resulting diagrams are available on his webpage.
The Complexity Zoo. A similar diagram for complexity classes in theoretical computer science can be found on Greg Kuperberg homepage. It is older and larger than the Computability Menagerie and was also constructed with computer assistance.
Giving a lecture
On top of Niesen, in Switzerland. For the record, I ascended by funicular, not foot.
Giving a lecture
In front of the Fajing (formally Daming) temple pagoda in Yangzhou, China.

October 29, 2015