How can I prove the languages of incompressible words is undecidable?
-
05-11-2019 - |
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$
- Enumerate over all $n$-bit strings $x$ in lexicographical order
- Simulate M on each $x$, where $M$ is the Turing machine that decides $L$.
- 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