Very roughly, the idea is that the prior probability that the universe is a (n+1) state Turing machine is half the prior probability that the universe is a n state Turing machine. Whereas the most anyone can offer you in a n state machine is BB(n) but the most they can offer you in a (n+1) state machine is BB(n+1)
So, again very roughly, the probability I can offer you BB(n) is roughly k2^(-n) where k is a very small constant. So the probability I can offer you m utility is roughly k2^(-inverseBB(n)).
InverseBB(n) is a monotonically increasing function that increases more slowly than any montonically increasing computable function, so k2^(-inverseBB(n)) is a monotonically decreasing function that decreases more slowly than any computable monotonically decreasing function.
To add to that explanation, you can prove that the number of people who can be simulated on a halting n-state Turing machine has no computable upper bound by considering a Turing machine that alternates between some computation and simulating humans every fixed number of steps. If we could compute an upper bound on the number of humans simulates we could compute whether the TM would halt by waiting for that many people to be simulated, similarly to how we could use BB(n) to determine whether any n-state TM will halt if we knew its value.
Huh, I don’t understand Solomonoff induction then. Explain?
Very roughly, the idea is that the prior probability that the universe is a (n+1) state Turing machine is half the prior probability that the universe is a n state Turing machine. Whereas the most anyone can offer you in a n state machine is BB(n) but the most they can offer you in a (n+1) state machine is BB(n+1)
So, again very roughly, the probability I can offer you BB(n) is roughly k2^(-n) where k is a very small constant. So the probability I can offer you m utility is roughly k2^(-inverseBB(n)).
InverseBB(n) is a monotonically increasing function that increases more slowly than any montonically increasing computable function, so k2^(-inverseBB(n)) is a monotonically decreasing function that decreases more slowly than any computable monotonically decreasing function.
Ooo, I get it! I was thinking of writing out the utility (log_base), but this is more general. Thanks!
To add to that explanation, you can prove that the number of people who can be simulated on a halting n-state Turing machine has no computable upper bound by considering a Turing machine that alternates between some computation and simulating humans every fixed number of steps. If we could compute an upper bound on the number of humans simulates we could compute whether the TM would halt by waiting for that many people to be simulated, similarly to how we could use BB(n) to determine whether any n-state TM will halt if we knew its value.