Mass problems associated with effectively closed sets (Q765664)

From MaRDI portal





scientific article; zbMATH DE number 6016704
Language Label Description Also known as
default for all languages
No label defined
    English
    Mass problems associated with effectively closed sets
    scientific article; zbMATH DE number 6016704

      Statements

      Mass problems associated with effectively closed sets (English)
      0 references
      0 references
      21 March 2012
      0 references
      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.
      0 references
      mass problems
      0 references
      unsolvable problems
      0 references
      degrees of unsolvability
      0 references
      Muchnik degrees
      0 references
      algorithmic randomness
      0 references
      Kolmogorov complexity
      0 references
      resource-bounded computational complexity
      0 references
      recursively enumerable degrees
      0 references
      hyperarithmetical hierarchy
      0 references
      intuitionism
      0 references
      proof theory
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references