Mass problems associated with effectively closed sets (Q765664): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:09, 5 March 2024
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
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