For more information about this meeting, contact Stephen Simpson.

Title: | Mass problems, part 1 |

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 / 03 / 2009 |

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