That may indeed end up being the best solution to the problem. On the other hand, what formal language do we write such definitions in? SI already has the limitation that you have to supply a basis of computation, the choice of which weakly affects the result (additive constant on Kolmogorov complexity (in practice small), multiplicative constant on measure). Is there a way to use definitions which are not necessarily algorithms, so as to get a formally precise result without making this limitation much worse?
It’s an attempt to make the limitation only that bad. They will only be guaranteed to differ by a constant if both languages are equivalent. If you choose between a Turing machine and a Turing machine with a halting oracle, the former will at best beat the latter by a constant, but the latter can beat the former infinitely.
You obviously can’t get it to work for all possible oracles, as there are uncountably infinite of them, but you can at least to it for all definable oracles, which is what this is.
That may indeed end up being the best solution to the problem. On the other hand, what formal language do we write such definitions in? SI already has the limitation that you have to supply a basis of computation, the choice of which weakly affects the result (additive constant on Kolmogorov complexity (in practice small), multiplicative constant on measure). Is there a way to use definitions which are not necessarily algorithms, so as to get a formally precise result without making this limitation much worse?
It’s an attempt to make the limitation only that bad. They will only be guaranteed to differ by a constant if both languages are equivalent. If you choose between a Turing machine and a Turing machine with a halting oracle, the former will at best beat the latter by a constant, but the latter can beat the former infinitely.
You obviously can’t get it to work for all possible oracles, as there are uncountably infinite of them, but you can at least to it for all definable oracles, which is what this is.