An enumerable undecidable set with low prefix complexity: a simplified proof
Nikolay Vereshchagin · 2001
e). To do so we start with n k = 2k (say) and with A = ;. Then we enumerate the graph of the function (p k ; n) 7! p k (n). If (for some k) we nd that p k (n k ) is dened and dierent from 0 we add n k to A. In this way we will obtain an enumerable undecidable set. However it may not satisfy the inequality KP(A 1:n ) KP(n) +O(1). To ensure this inequality let us rst rewrite it using a priori distribution m(z) as follows: m(A 1:n ) m(n)=c for some positive c and all