1

Given a finite sequence $a_1, \dots , a_n$ over $\{0,1\}$ define a recursive formula of the sequence as a set of initial conditions and general recursion formula, e.g. $a_n = 2a_{n-1} + (1+n)^n \pmod 2$, which is allowed to use the operations addition, subtraction, multiplication, division and power with any complex arguments such that they describe the sequence.

Given a finite sequence $a_1, \dots , a_n$ over $\{0,1\}$ define the size of a recursive form as the number of initial conditions $+$ the number of operations in the corresponding general recursive formula.

There exists a minimal one, since given a general sequence we can take $n-1$ initial conditions and a general formula only for the last element (or just take the empty formula with $n$ initial conditions which will be of size $n$).

Some sequences clearly have a constant size formula, e.g the sequence $0,0, \dots, 0$ has the recursive formula $a_n =0$ with no initial conditions which has size $0$.

What is the general minimal size of a recursive formula defined as above for an arbitrary sequence of length $n$ (i.e a tight upper bound)?

Not sure how well known/studied this question is and will be happy for any help and related topics that have been studied.

user10364768
  • 213
  • 2
    This is related to Kolmogorov complexity. The Kolmogorov complexity of a string is, informally, "the length of the shortest description of the string". Formally, a description of a string $s$ is a string $s'$ representing an algorithm that computes $s$. – Mark Saving Aug 13 '21 at 20:24
  • 1
    They say there is no archiver that would compress every single file of length $n$ into an archive of length strictly less than $n$. That's your lower bound. – Ivan Neretin Aug 13 '21 at 20:24

0 Answers0