Degrees of unsolvability: a two-hour tutorial

Stephen G. Simpson

Department of Mathematics, Pennsylvania State University

Department of Mathematics, Vanderbilt University http://www.math.psu.edu/simpson/ stephen.g.simpson@vanderbilt.edu sgslogic@gmail.com

September 23, 2016

This is my abstract for Computability Theory and Foundations of Mathematics (CTFM 2016), Waseda University and Tokyo Institute of Technology, September 20–23, 2016.

Given a problem P, one associates to P a degree of unsolvability, denoted deg(P). Here deg(P) is a quantity which measures the “difficulty” of P, i.e., the amount of algorithmic unsolvability which is inherent in P. We focus on two degree structures: the semilattice of Turing degrees, D_{T}, and its completion, D_{w} = D̂_{T}, the lattice of Muchnik degrees. We remark that D_{w} gives rise to a natural recursion-theoretic interpretation of Kolmogorov’s non-rigorous “calculus of problems.” We emphasize the analogy between E_{T}, the countable subsemilattice of D_{T} consisting of the Turing degrees associated with recursively enumerable subsets of ℕ, and E_{w}, the countable sublattice of D_{w} consisting of the Muchnik degrees associated with nonempty Π_{1}^{0} subsets of {0, 1}^{ℕ}. We emphasize specific, natural degrees in D_{T}, D_{w}, and E_{w}.