The Computability MenagerieThe menagerie is a dynamic diagram of (downward closed) classes of Turing degrees. It is easy to use; just follow the link below and explore.
HistoryBetween 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 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).