Question

Show that the set of incompressible strings contains no infinite subset that is Turing-recognizable.

Short answer

Turing-Recognizable subset of incompressible strings doesn’t exist.

Step-by-step solution

Turing Recognizable

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e. Turing Machine halt and accept strings belong to language L and will reject or not halt on the input strings that doesn’t belong to language L.

Proving Turing-Recognizable subset of incompressible strings doesn’t exist

Let’s prove the above statement by contradiction.

So, let there is infinite subset S of incompressible strings.

Let M be the Turing Machine that recognize S. We will construct a Turing Machine P as follows:

• Obtain its description ‹P›
• Repeat S, until it finds a string x whose length is greater than $‹P,\in ›i.e.,\left|x\right|>|‹P,\in ›|.$
• Output: x .

S must contain strings which are larger than |‹P›| in terms of length because length of each string in S must be infinite. Therefore, description of x must be $‹P,\in ›$implies: $K\left(x\right)\le |‹P,\in ›|<\left|x\right|.$

But it must be noted that x is an incompressible string, so our above assumption is contradict.

Hence, there exist no infinite Turing-Recognizable subset of incompressible strings.