Tohoku Mathematical Journal
2011
December
SECOND SERIES VOL. 63, NO. 4

Tohoku Math. J.
63 (2011), 489-517

Title MASS PROBLEMS ASSOCIATED WITH EFFECTIVELY CLOSED SETS

Author Stephen G. Simpson

(Received December 17, 2010)
Abstract. The study of mass problems and Muchnik degrees was originally motivated by Kolmogorov's non-rigorous 1932 interpretation of intuitionism as a calculus of problems. The purpose of this paper is to summarize recent investigations into the lattice of Muchnik degrees of nonempty effectively closed sets in Euclidean space. Let $\mathcal{E}_\mathrm{w}$ be this lattice. We show that $\mathcal{E}_\mathrm{w}$ provides an elegant and useful framework for the classification of certain foundationally interesting problems which are algorithmically unsolvable. We exhibit some specific degrees in $\mathcal{E}_\mathrm{w}$ which are associated with such problems. In addition, we present some structural results concerning the lattice $\mathcal{E}_\mathrm{w}$. One of these results answers a question which arises naturally from the Kolmogorov interpretation. Finally, we show how $\mathcal{E}_\mathrm{w}$ can be applied in symbolic dynamics, toward the classification of tiling problems and $\boldsymbol{Z}^d$-subshifts of finite type.

2000 Mathematics Subject Classification. Primary 03D30; Secondary 03D20, 03D25, 03D28, 03D32, 03D55, 03D80, 37B10.
Key words and phrases. Mass problems, unsolvable problems, degrees of unsolvability, Muchnik degrees, algorithmic randomness, Kolmogorov complexity, resourse-bounded computational complexity, recursively enumerable degrees, hyperarithmetical hierarchy, intuitionism, proof theory, symbolic dynamics.

To the top of this page

Back to the Contents