The optimal “A” in my question is a way of assigning probabilities to hypotheses of the form “word x belongs to NP-language X” which are efficiently computable (also, I believe it is possible to extend this at least to languages in L^NP).
Consider a sentence phi in some formal theory T. For any given k, the hypothesis that phi is provable in T by a proof of length at most k is of the above form. The same is true of not-phi. This way we can assign phi the probability
P_k(phi) = P(phi has a proof of length ⇐ k) / (P(phi has a proof of length ⇐ k) + P(not-phi has a proof of length ⇐ k))
It is not hard to see that the properties of A imply that P_k(phi) → 0⁄1 when k->infinity for consistent T and phi refutable/provable in T.
I think this establishes some relevance to logical uncertainty in the “classical” sense but it doesn’t seem to solve tiling agents since it is still restricted to reasoning within a fixed theory T. However, there are other reasons why NP-estimators might be able to solve tiling agents.
One way to think of the tiling agents problem is the computational impossibility of simulating the successor agent in reasonable time. Now, suppose that we put some restrictions on the form of agents that we allow, namely that our agents are search algorithms that divide the strategy space into “chunks” and perform optimization within each chunk in some way (which can be anything). In the end, the best out of all found strategies is selected. If the parent agent knew which chunk the child agent would select it would be able to simulate it by running it on one chunk only. However, our NP-estimator allows getting rid of exactly the type of exponential slow-downs that the multitude of chunks creates enabling the parent to perform a probabilistic “pseudosimulation”.
Possibly this logic can be generalized to show that the estimator can be used to estimate in logarithmic time any computation within NC, thus allowing any agent algorithm as long as it’s sufficiently parallelizable. This requires further thought.
It also should be possible to use A directly to construct an efficiently computable approximation of Solomonoff induction. Namely, once we introduce a cutoff on the runtime of the hypotheses we allow within our Solomonoff ensemble, computing Solomonoff induction amounts to a counting problem. However, counting problems have efficient approximations modulo an NP-oracle and it seems that it’s possible to replace the oracle by a “probability assigner” to yield an efficient (but obviously less accurate) approximation in P.
This computable induction can be used to remove another obstruction of “pseudosimulating” the child agent, namely the unknown behavior of the environment in the future.
The optimal “A” in my question is a way of assigning probabilities to hypotheses of the form “word x belongs to NP-language X” which are efficiently computable (also, I believe it is possible to extend this at least to languages in L^NP).
Consider a sentence phi in some formal theory T. For any given k, the hypothesis that phi is provable in T by a proof of length at most k is of the above form. The same is true of not-phi. This way we can assign phi the probability
P_k(phi) = P(phi has a proof of length ⇐ k) / (P(phi has a proof of length ⇐ k) + P(not-phi has a proof of length ⇐ k))
It is not hard to see that the properties of A imply that P_k(phi) → 0⁄1 when k->infinity for consistent T and phi refutable/provable in T.
I think this establishes some relevance to logical uncertainty in the “classical” sense but it doesn’t seem to solve tiling agents since it is still restricted to reasoning within a fixed theory T. However, there are other reasons why NP-estimators might be able to solve tiling agents.
One way to think of the tiling agents problem is the computational impossibility of simulating the successor agent in reasonable time. Now, suppose that we put some restrictions on the form of agents that we allow, namely that our agents are search algorithms that divide the strategy space into “chunks” and perform optimization within each chunk in some way (which can be anything). In the end, the best out of all found strategies is selected. If the parent agent knew which chunk the child agent would select it would be able to simulate it by running it on one chunk only. However, our NP-estimator allows getting rid of exactly the type of exponential slow-downs that the multitude of chunks creates enabling the parent to perform a probabilistic “pseudosimulation”.
Possibly this logic can be generalized to show that the estimator can be used to estimate in logarithmic time any computation within NC, thus allowing any agent algorithm as long as it’s sufficiently parallelizable. This requires further thought.
It also should be possible to use A directly to construct an efficiently computable approximation of Solomonoff induction. Namely, once we introduce a cutoff on the runtime of the hypotheses we allow within our Solomonoff ensemble, computing Solomonoff induction amounts to a counting problem. However, counting problems have efficient approximations modulo an NP-oracle and it seems that it’s possible to replace the oracle by a “probability assigner” to yield an efficient (but obviously less accurate) approximation in P.
This computable induction can be used to remove another obstruction of “pseudosimulating” the child agent, namely the unknown behavior of the environment in the future.