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$ Oct 22, 2017 at 6:37
  • $\begingroup$ Edit, top -> HALT and membership problem. $\endgroup$
    – afdez
    Oct 22, 2017 at 12:56

1 Answer 1


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.

  • $\begingroup$ But doesn't the output of a Turingmaschine depend on the input, meaning if you test the first Turing machine (that with shortest encoding), wouldn't you have to test all inputs on it? $\endgroup$
    – Jacob
    Dec 3, 2021 at 15:32
  • $\begingroup$ Kolmogorov complexity is defined using inputless Turing machines. $\endgroup$ Dec 3, 2021 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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