Effective simultaneous approximability of reals. (Q1607296)

The effective simultaneous approximability of real vectors and sets of reals is studied. A hierarchy of real vectors based on the Kolmogorov complexity of computable approximations is constructed. We prove that the hierarchy is nontrivial at the bottom levels but collapses on the top levels. A hierarchy theorem which gives a simple test for proper inclusion between two classes is established. We also show that an effective approximation problem for a finite set may be hard (have no computable solutions) when the corresponding problems for all its proper subsets are simple (have computable solutions).