91Ó°ÊÓ

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.

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,∈›i.e.,\left|x\right|>|‹P,∈›|.$
• 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,∈›$implies: $K\left(x\right)≤|‹P,∈›|<\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.