3 ms·
Even if we limit it to primitive recursive functions, how can we put a bound on the Kolmogorov complexity of one? We'd need some way of coming up with bounds on
by jey 17y ago
Even if we limit it to primitive recursive functions, how can we put a bound on the Kolmogorov complexity of one? We'd need some way of coming up with bounds on the smallest Turing machine to compute that function.
- eru 17y agoThat might be possible. Primitive recursion is much less powerful than Turing machines.