4 ms·
> the shortest equation That in itself is computationally impossible [1] but I guess "reasonably short" will do just fine. [1] http://en.wikipedia.org/wiki/Ko
by wlievens 15y ago
> the shortest equation
That in itself is computationally impossible [1] but I guess "reasonably short" will do just fine.
[1] http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity
- Someone 15y agoI disagree; as I indicated, it is easy to find one equation. Once you have one, enumerate all possible equations up to the length of the equation you found, and check them. Assuming a finite alphabet, that set is finite, so if checking whether a function's plot resembles the target text is computable, finding the set of shortest solutions is. If checking a candidate is not computable, Kolmogorov complexity would rear its head, but I do not think the problem of finding the shorter equation is well-defined in that case.
- wlievens 15y agoThat only holds if all your formula are guaranteed to halt. I guess that's true if they're limited to arithmetic functions, without looping or recursion of any kind. Also do note that what you're saying is only easy in theory. In practice it could take years to find your shorter formula.