For more information about this meeting, contact Stephen Simpson.

Title: | Mass problems, part 2 |

Seminar: | Logic Seminar |

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

Abstract: |

Kolmogorov 1932 proposed to view intuitionistic logic as a ``calculus of problems'' (Aufgabenrechnung). This is essentially the famous BHK interpretation of intuitionism. Medvedev 1955 introduced mass problems as a rigorous elaboration of Kolmogorov's proposal. A \emph{Turing oracle} is a point in Euclidean space. A \emph{mass problem} is a set of Turing oracles. If $A$ is a mass problem, the \emph{solutions} of $A$ are the elements of $A$. We say that $A$ is \emph{solvable} if there exists a computable solution of $A$. We say that $A$ is \emph{weakly reducible} to $B$ if each solution of $B$ can be used as a Turing oracle to compute some solution of $A$. A \emph{weak degree} is an equivalence class of mass problems under mutual weak reducibility. Let $\mathcal{D}_w$ be the lattice of weak degrees. Muchnik 1963 observed that $\mathcal{D}_w$ is a model of intuitionistic propositional calculus. Since 1999 I have been studying the sublattice $\mathcal{P}_w$ consisting of the weak degrees of nonempty effectively closed sets in Euclidean space. I discovered a natural embedding of the recursively enumerable Turing degrees into $\mathcal{P}_w$. Moreover, I discovered that $\mathcal{P}_w$ contains a variety of specific, natural, weak degrees which are closely related to various foundationally interesting topics. Among these topics are reverse mathematics, algorithmic randomness, algorithmic information theory, hyperarithmeticity, diagonal nonrecursiveness, almost everywhere domination, subrecursive hierarchies, resource-bounded computational complexity, effective Hausdorff dimension, and Kolmogorov complexity. Recently I applied $\mathcal{P}_w$ to the study of 2-dimensional symbolic dynamics. The purpose of this talk is to introduce $\mathcal{P}_w$ and survey what is known about it. |

### Room Reservation Information

Room Number: | MB315 |

Date: | 02 / 10 / 2009 |

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