Introduction to mass problems

Logic Seminar

Meeting Details

For more information about this meeting, contact Stephen G. Simpson.

Speaker: Stephen G. Simpson, Pennsylvania State University

Abstract: In an important and influential 1932 paper, Kolmogorov proposed a "calculus of problems" and noted its similarity to the intuitionistic propositional calculus of Brouwer and Heyting. According to Kolmogorov's informal idea, one problem is said to be "reducible" to another if any solution of the second problem can easily be transformed into a solution of the first problem. In 1955 Kolmogorov's doctoral student Medvedev developed a rigorous, elaboration of Kolmogorov's informal idea, in terms of Turing's theory of computability and unsolvability. A mass problem was defined to be a set of Turing oracles, i.e., an arbitrary subset of the Cantor space. A mass problem was said to be solvable if it contains at least one computable member. One mass problem was said to be reducible to another if there exists a partial computable functional carrying all members of the second problem to members of the first problem. This reducibility notion is now known as strong reducibility, in contrast to the weak reducibility of Muchnik 1963, who required only that for each member of the second problem there exists a member of the first problem which is Turing reducible to it. On this basis Medvedev and Muchnik respectively noted that the strong and weak degrees of unsolvability form Brouwerian lattices. Subsequently these lattices turned out to be an extremely useful tool in the classification of unsolvable problems arising in several areas of mathematics, including most recently dynamical systems. The purpose of this talk is to introduce these ideas, which will be elaborated further in subsequent talks.

Room Reservation Information

Room Number: 106 McAllister

Date: 10/16/2007

Time: 2:30pm - 3:45pm