I try to solve the following exercise:

We know that K (x), the complexity of Kolmogorov, is incomputable. Show how calculate it, if we have an oracle for the membership problem (or for the HALT problem, if it accommodates more).

I have solved it in the following way:

Let (w) be the string to which I compute K (w).

(1). I have a TM 'G', which generates TM descriptions in order of length 'Mi'.

(2). The generated descriptions 'Mi' and (w) are inputs of a TM that has a Oracle for the Membership Problem TMO 'Memb'.

     * If TMO 'Memb' rejects then TM 'G' generates a new description Mi + 1, returns to step (1).      * If you accept this description Mi and (w), they pass as input to the TM 'R', go to step (3).

(3). TM 'R' runs the description Mi with input (w) and prints the number of steps (t).

(4). Then K(w) would be |< Mi >| + t

enter image description here

It would be necessary to run TM 'R' or I can replace the problem of the Membership with the one of the HALT Problem and this gives me that number of steps that I calculate with TM 'R'?


  • $\begingroup$ What are the membership problem and the top problem? $\endgroup$ – Yuval Filmus Oct 22 '17 at 6:37
  • $\begingroup$ Edit, top -> HALT and membership problem. $\endgroup$ – Alejandro Fernandez Oct 22 '17 at 12:56

Here is the idea. Given a string $x$ whose Kolmogorov complexity you want to calculate, go over all programs in non-decreasing order of length. For each program $p$, check using the oracle whether it halts, and if so, check whether it outputs $x$. If it does, the Kolmogorov complexity is the length of $p$. Otherwise, go to the next program. Eventually you will find a program computing $x$. The program you will find is a shortest one since we go over all programs in non-decreasing order of length.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.