<p>Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using <strong>optimization methods</strong> (gradient descent, genetic algorithms, etc)?</p>
<p>In theoretical computer science, I read about methods which search iteratively amongst all programs (like Levin search <a href="http://www.scholarpedia.org/article/Universal_search" rel="nofollow noreferrer">http://www.scholarpedia.org/article/Universal_search</a>), but I was wondering if methods using optimization could, in some cases, find solutions faster ?</p>
<p>For instance we could describe a program by an LSTM [1], trained to produce the string, but with a regularization that encourages the weights of the LSTM itself to be simple to code (for instance encouraging sparsity).</p>
<p>In Machine Learning, there are many works trying to encode a dataset with a simple model (using the Minimum Description Length theory for instance), although in most cases the models they consider are not Turing complete because they are feedforward network [6]: for instance works like [7].
On the other hand, there are programs that intend to learn a Turing machine (like [2]), which are Turing complete [5], but in this case I'm not aware of any work trying to reduce the complexity of encoding the model themselves (except maybe this work [4]).</p>
<p><strong>Question:</strong> Has there been some works on short program search using optimization methods, and ideally that give guarantees on how close we can be to the (resource bounded) Kolmogorov complexity after <span class="math-container">$t$</span> iterations ? From my understanding, finding an explicit program to compress a string gives an upper bound on the Kolmogorov complexity of the string, which is good, but I was wondering if there could be guarantees like in say convex optimization, of the type: after <span class="math-container">$t$</span> iterations of the search/optimization, we are guaranteed to be this <span class="math-container">$\epsilon$</span> close to the true resource bounded Kolmogorov complexity. More generally, I'm curious of any related work in this area.</p>
<p>[1] <a href="https://en.wikipedia.org/wiki/Long_short-term_memory" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Long_short-term_memory</a></p>
<p>[2] &quot;Neural Turing Machines&quot; <a href="https://arxiv.org/abs/1410.5401" rel="nofollow noreferrer">https://arxiv.org/abs/1410.5401</a></p>
<p>[3] Differentiable Neural Computer: <a href="https://deepmind.com/blog/article/differentiable-neural-computers" rel="nofollow noreferrer">https://deepmind.com/blog/article/differentiable-neural-computers</a></p>
<p>[4] &quot;Neural Abstract reasoner&quot; <a href="https://arxiv.org/abs/2011.09860" rel="nofollow noreferrer">https://arxiv.org/abs/2011.09860</a></p>
<p>[5] &quot;On the Turing completeness of modern neural networks architectures&quot; <a href="https://openreview.net/pdf?id=HyGBdo0qFm" rel="nofollow noreferrer">https://openreview.net/pdf?id=HyGBdo0qFm</a></p>
<p>[6] <a href="https://stackoverflow.com/a/20950522/15569217">https://stackoverflow.com/a/20950522/15569217</a></p>
<p>[7] Keeping the neural networks simple by minimizing the description length of the weights <a href="https://dl.acm.org/doi/10.1145/168304.168306" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/168304.168306</a></p>

CC BY-SA 4.0
2021-04-28T20:54:40.587Z
Not directly in the context of Kolmogorov complexity, but [Chris Cummins](https://chriscummins.cc/cv/) has been working on generating programs using deep learning. I don't know what the state of the art is in 2021, but IIRC in the past  the generated programs were not necessarily syntactically correct, so had to be filtered by compilation.
Martin Berger
CC BY-SA 4.0
2021-05-06T15:01:26.590Z
Thanks for your comment ! This looks interesting, I’ll have a look.
dorikolmo
<reference-request><optimization><kolmogorov-complexity><convex-optimization>
program search with optimization methods for (resource bounded) Kolmogorov complexity
dorikolmo
# program search with optimization methods for (resource bounded) Kolmogorov complexity

(Asked by: username_0 on 2021-04-28)

Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using **optimization methods** (gradient descent, genetic algorithms, etc)?

In theoretical computer science, I read about methods which search iteratively amongst all programs (like Levin search <http://www.scholarpedia.org/article/Universal_search>), but I was wondering if methods using optimization could, in some cases, find solutions faster ?

For instance we could describe a program by an LSTM [1], trained to produce the string, but with a regularization that encourages the weights of the LSTM itself to be simple to code (for instance encouraging sparsity).

In Machine Learning, there are many works trying to encode a dataset with a simple model (using the Minimum Description Length theory for instance), although in most cases the models they consider are not Turing complete because they are feedforward network [6]: for instance works like [7].
On the other hand, there are programs that intend to learn a Turing machine (like [2]), which are Turing complete [5], but in this case I'm not aware of any work trying to reduce the complexity of encoding the model themselves (except maybe this work [4]).

**Question:** Has there been some works on short program search using optimization methods, and ideally that give guarantees on how close we can be to the (resource bounded) Kolmogorov complexity after $t$ iterations ? From my understanding, finding an explicit program to compress a string gives an upper bound on the Kolmogorov complexity of the string, which is good, but I was wondering if there could be guarantees like in say convex optimization, of the type: after $t$ iterations of the search/optimization, we are guaranteed to be this $\epsilon$ close to the true resource bounded Kolmogorov complexity. More generally, I'm curious of any related work in this area.

[1] <https://en.wikipedia.org/wiki/Long_short-term_memory>

[2] "Neural Turing Machines" <https://arxiv.org/abs/1410.5401>

[3] Differentiable Neural Computer: <https://deepmind.com/blog/article/differentiable-neural-computers>

[4] "Neural Abstract reasoner" <https://arxiv.org/abs/2011.09860>

[5] "On the Turing completeness of modern neural networks architectures" <https://openreview.net/pdf?id=HyGBdo0qFm>

[6] <https://stackoverflow.com/a/20950522/15569217>

[7] Keeping the neural networks simple by minimizing the description length of the weights <https://dl.acm.org/doi/10.1145/168304.168306>

**Tags:** reference-request, optimization, kolmogorov-complexity, convex-optimization

> **Comments:**
> **username_1**: Not directly in the context of Kolmogorov complexity, but [Chris Cummins](https://chriscummins.cc/cv/) has been working on generating programs using deep learning. I don't know what the state of the art is in 2021, but IIRC in the past  the generated programs were not necessarily syntactically correct, so had to be filtered by compilation.  
> **username_0**: Thanks for your comment ! This looks interesting, I’ll have a look.  

---

## 0 answers

