Question

I have hard time understanding the proof by contradiction for the claim "$L=\{x : K(x) \ge |x| \}$" is undecidable ".

The proof is as follows :

M' = " On input $n$

  1. Enumerate over all $n$-bit strings $x$ in lexicographical order
  2. Simulate M on each $x$, where $M$ is the Turing machine that decides $L$.
  3. Output first $x$ which $M$ accepts. "

Since TM $M'$ produced incompressible using only $O(\log n)$ to specify $n$, we can compress incompressible strings which is a contradiction.

I understood the $M'$ construction. However, I do not understand where exactly is the contradiction happening? According to me, $M'$ outputs $x$ which is in-compressible(ensured by TM $M$) but how does it is also compressible at same time?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top