> Roughly speaking, the complexity of an object is the length of its shortest description. This has a ton of really interesting implications. Even though Kolm

> Roughly speaking, the complexity of an object is the length of its shortest description. This has a ton of really interesting implications. Even though Kolmogorov complexity is technically incomputable due to the halting problem, you can estimate it. One method of doing that is to create a bunch of random Turing machines and see how often they produce some output string[1]. You have to cut them off after running for a while to prevent infinite loops but it turns out that the output probability of a string strongly correlates with its Kolmogorov complexity. This works for neural networks as well. You can treat a neural network as a binary classifier, or more generally a boolean function that has some number of binarized inputs mapping to a single binary output. I explored this a bit in a blog post I wrote a while ago[2]. By randomly initializing weights and counting the truth tables produced, you can estimate Boolean complexity for different expressions which is NP hard. [1] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4014489/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4014489/ [2] https://cprimozic.net/blog/boolean-logic-with-neural-networks/#estimating-boolean-complexity https://cprimozic.net/blog/boolean-logic-with-neural-network...