Mass problems associated with effectively closed sets (Q765664)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Mass problems associated with effectively closed sets
scientific article

    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references