What if we let AIXI play game 1, and allow probabilities to be written in some specific non-computable notation, such as a programming language that allows calls to a halting oracle. Does AIXI win this game?
How does AIXI play regular game 1? Finite binary notation isn’t enough to specify the uncomputable probability values it wants to output.
If we handwave this difficulty away and say that the AI’s output may include infinite sums etc., then there’s a simple agent that avoids losing your game by more than a constant: the mixture of all computable consistent mixtures expressible in your notation. Proof of optimality is unchanged.
On the other hand, if only finite notation is allowed, then it’s not clear what AIXI is supposed to output at each step. The AIXI paper would advise us to construct the optimal agent tailor-made for your game, using a universal prior over computable input sequences. I have no idea how such an agent would fare on uncomputable input.
An idea from discussion with cousin_it:
What if we let AIXI play game 1, and allow probabilities to be written in some specific non-computable notation, such as a programming language that allows calls to a halting oracle. Does AIXI win this game?
How does AIXI play regular game 1? Finite binary notation isn’t enough to specify the uncomputable probability values it wants to output.
If we handwave this difficulty away and say that the AI’s output may include infinite sums etc., then there’s a simple agent that avoids losing your game by more than a constant: the mixture of all computable consistent mixtures expressible in your notation. Proof of optimality is unchanged.
On the other hand, if only finite notation is allowed, then it’s not clear what AIXI is supposed to output at each step. The AIXI paper would advise us to construct the optimal agent tailor-made for your game, using a universal prior over computable input sequences. I have no idea how such an agent would fare on uncomputable input.