Question

Show that the set of incompressible strings is undecidable.

Short answer

It is proven that incompressible strings are undecidable.

Step-by-step solution

Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Proving the result

Let there be a string w_i such that it doesn’t have description shorter then itself.

This implies that w_i is incompressible.

We will assume a set of incompressible strings as A and consider A as decidable.

Now we will design a Turing Machine M that enumerates A as follows:

$f:A\to N$

Here, $f\left(w_1\right)=1,f\left(w_2\right)=2\dots .$and so on.

So, $w_iєA$

Now we will construct a Turing Machine which computes w_iof length n as follows:

$T=oninput‹M,w›$

• Return first string w_iwhich enumerated by M
• If $K(‹T,n›)=c+\log \left(n\right)$
• So we can find n such that:

Length .$\left(w_i\right)=n>c+lo{g}_2\left(n\right).$

Now string w_i has shorter description on $‹M’,f\left(w_i\right)›,$where M’ being Turing Machine and f(w_i) and w_ibeing output. Now run M’ each string in lexicographic order and output same from Turing Machine M. Now, it will be contradiction that w_iis compressible. So, our assumption of A being decidable is wrong.

Thus, for a set of incompressible strings A, and A will be undecidable.