Mass problems associated with effectively closed sets (Q765664): Difference between revisions

In the paper recent investigations into the lattice of Muchnik degrees of nonempty effectively closed sets in Euclidean space \({\mathcal E}_{w}\) are summerized. In particular it is shown that \({\mathcal E}_{w}\) provides an elegant and useful framework for the classification of certain foundationally interesting problems which are algorithmically unsolvable. Some specific degrees in \({\mathcal E}_{w}\) which are associated with such problems are exhibited. Additionally, some structural results concerning the lattice \({\mathcal E}_{w}\) are presented. One of them gives an answer to a question which arises naturally from the Kolmogorov non-rigorous 1932 interpretation of intuitionism as a calculus of problems. It is also shown how \({\mathcal E}_{w}\) can be applied in symbolic dynamics toward the classification of tiling problems and \({\mathbb Z}^{d}\)-subshifts of finite type.