For more information about this meeting, contact Stephen Simpson, Jan Reimann, Jason Rute.

Title: | Degrees of unsolvability: a survey. |

Seminar: | Logic Seminar |

Speaker: | Stephen G. Simpson, Pennsylvania State University |

Abstract: |

In 1936 Turing produced the first example of a mathematical problem which is algorithmically unsolvable. This was followed by various attempts to classify such problems according to their degrees of unsolvability, i.e., the amount of algorithmic unsolvability which is inherent in them. The theory of Turing degrees applies to decision problems and is very rich, but unfortunately not very useful for the original purpose. The more recent theory of Muchnik degrees applies to a more general class of problems known as mass problems, and is therefore much more relevant in this respect. Recent investigations have revealed many examples of natural, specific, Muchnik degrees which can be used to classify unsolvable problems arising in various contexts, especially algorithmic randomness and reverse mathematics. I will survey various results of this type. I will also announce a structural result, to the effect that the lattice of Muchnik degrees of effectively closed sets is dense. This new result will appear in a joint paper by Binns, Shore, and myself. |

### Room Reservation Information

Room Number: | MB315 |

Date: | 04 / 01 / 2014 |

Time: | 02:30pm - 03:45pm |