23 ms·

Oh but that was specifically what I was trying to get at, i.e. point #4 of this reply of yours: Are there any shortcuts that make this reasonably computable or

by anyfoo 2y ago

Oh but that was specifically what I was trying to get at, i.e. point #4 of this reply of yours: Are there any shortcuts that make this reasonably computable or not? In your original reply, you started with (transcribing) "Kolmogorov complexity is not technically uncomputable in the practical case of not having an infinite tape", which gave me hope that we would start talking about how there are some reasonable shortcuts in this particular case (as you mention in this answer now). But then you ended with (literally) "That said, in practice it would probably take an unreasonable amount of time to perform this computation (but that is orthogonal to whether it's computable or not)", which squashed my hopes, seemed to just have replaced "theoretically uncomputable" with "practically uncomputable", and made me wonder how it changed anything that OP already wrote in practical terms, namely: "Unfortunately, that's uncomputable" But now it seems we're back to (potentially) discussing how in this particular use case there might be tractable ways to (limited, but useful) computability, which is good again!

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...

by anyfoo 2y ago

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...