91影视

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

Let there be a string w_i such that it doesn鈥檛 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鈫�N$

Here, $f\left(w_1\right)=1,f\left(w_2\right)=2鈥�.$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.