I see no reason why Solominoff Induction can’t just use definitions, and it’s perfectly possible to define a halting oracle in a finite space.
If we are stuck with algorithms, why would we be allowed to use NOR as a command, but not a halting oracle? There’s nothing wrong with the idea of a universe where the former isn’t possible, nor with a universe where the latter 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.
I see no reason why Solominoff Induction can’t just use definitions, and it’s perfectly possible to define a halting oracle in a finite space.
If we are stuck with algorithms, why would we be allowed to use NOR as a command, but not a halting oracle? There’s nothing wrong with the idea of a universe where the former isn’t possible, nor with a universe where the latter 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.