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
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'?