3 ms·
I should note that I'm not a computer scientist and I'm currently a bit sleep-deprived, but to continue discussing what you're interested in: I tend to think t
by someplaceguy 2y ago
I should note that I'm not a computer scientist and I'm currently a bit sleep-deprived, but to continue discussing what you're interested in:
I tend to think that an efficient computation of some finite-state version of Kolmogorov complexity would necessarily require an efficient computation of a finite-state version of the halting problem, but I'm not entirely sure of this.
Naively, it seems that this Kolmogorov calculation would require enumerating all programs (in increasing program size) and then running each of them until they either 1) enter an infinite loop, 2) produce the input string and halt, or 3) start producing a different string.
However, I'm not sure this would be the most efficient algorithm. For example, it might be easy to inspect each program and discard almost all that would "obviously" not produce the input string before we even try to run them.
Or better yet, never even enumerate such programs that can be proven not to produce the input string. In other words, cut the search space significantly.
Perhaps there might even be a shortcut to directly construct the smallest program that produces a given string, or at least, a family of small candidate programs that would be a very small subset of all possible programs and yet would be guaranteed to contain the solution.
As you might have noticed, unfortunately I don't know if there are such extraordinarily efficient shortcuts, I'm only speculating that they might exist.
That said, I still suspect that this might be intractable due to having to account for the worst case, i.e. undecipherable random-looking programs. In the case of the halting problem in the context of formal verification, I'm more optimistic since we usually don't need to care about such random-looking programs, only human-constructed ones (usually), which might be far easier to analyze algorithmically. I don't know if that makes sense...