LFS Kolmogorov Randomness

Question

Consider following LFS register (where + denotes addition modulo 2)

I have found the output sequence as 1,0,1,1.

I know that The K(s) of a string s is defined as the length of the shortest computer program that generates s and given a non-negative integer c,s incompressible if K(S)>= |s|- c.

My question is:

Is the output sequence Kolmogorov - random?

I could not understand how to find c or s in this question.

Answer 1

Edit: Kolmogorov complexity is most useful as an asymptotic concept as $n$, the length of the string increases. This is addressed in the general answer below.

Specifically one should use $s=1,0,1,1,1,0,0$ as the output, as suggested in the comments. Then the length is $|s|=7,$ and the question becomes

Is there a $c\geq 1,$ such that $K(s)\geq |s|-c$?

Since this string is woefully short, the answer is No, the program length would be too large, as pointed out in the comment by @PaulUszak.

General Answer:

Given any linear (or nonlinear) shift register of fixed length $L$ and its output sequence $(x_k)_{k=1}^n $, its Kolmogorov complexity is $o(n)$ (thus not Kolmogorov random) since the program which says essentially:

1. Let $i=1.$
2. Load register with $x_i,\ldots,x_{i+L-1}$
3. Compute output bit $z_i=f(x_1,\ldots,x_L)$ and output it
4. Compute state update bit $x_{i+L}=f(x_i,\ldots,x_{i+L-1})$
5. Update state to $(x_{i+1},\ldots,x_{i+L})$
6. $i\leftarrow i+1$
7. If $i>n$ Output $(x_1,\ldots,x_n)$ and Halt else Go to 2,

can generate a sequence of arbitrary length $n$ while $L$ is fixed.

More precisely, since the set of all functions $f:\{0,1\}^L \rightarrow \{0,1\}^L$ has cardinality $(2^L)^{2^L}=2^{L2^L}$ we can specify $f$ with $L2^L$ bits.

The program, and its input, obviously have length $O(L)$ bits. So the program complexity in bits is dominated by the $f$ specification.

Thus as $n\rightarrow \infty$ there is no finite constant $c,$ such that

$$K(z_1,\ldots,z_n)=O(L2^L) \geq n-c$$ holds. Hence the output is not Kolmogorov random.