2
$\begingroup$

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

enter image description here

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.

$\endgroup$
1
  • 1
    $\begingroup$ The output sequence really is 1,0,1,1,1,0,0, of length $7=2^3-1$. That must be the length since the generating polynomial is $x^3+x+1$, which it is primitive, and the initial state is not all-zero. $\endgroup$
    – fgrieu
    Oct 22, 2018 at 17:40

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Any nonnegative constant will do $\endgroup$
    – kodlu
    Sep 23, 2018 at 13:13
  • $\begingroup$ @M.J.Watson does this answer your question? $\endgroup$
    – kodlu
    Sep 29, 2018 at 13:38
  • $\begingroup$ Have to disagree. You've only given a general case solution to a very specific question which flips the answer. The above sequence clearly is K random as it's shorter than the op codes necessary to fully encode your 7 steps. You only have 3 bits for code to play with given you have to seed with "101". $\endgroup$
    – Paul Uszak
    Aug 19, 2019 at 12:04
  • $\begingroup$ Since the program required to encode an ever increasingly complex polynomial gets longer and longer, and it's output space gets longer and longer, it would be interesting to obtain an approximation of the smallest LRSF that becomes not K random. There must be a point of convergence somewhere... $\endgroup$
    – Paul Uszak
    Aug 20, 2019 at 12:06
  • $\begingroup$ A single binary polynomial of degree $t$ can be specified by $t+1$ bits and if well chosen have output of length $2^t-1.$ A randomly chosen polynomial won't have much lower output period either, it will still be exponential in $t$. $\endgroup$
    – kodlu
    Aug 20, 2019 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.