A Universal Intelligence Measure for Arithmetical Uncomputable Environments

We propose an extension to Legg and Hutter’s universal intelligence (UI) measure to capture the intelligence of agents that operate in uncomputable environments that can be classified on the Arithmetical Hierarchy. Our measure is based on computable environments relativized to a (potentially uncomputable) oracle. We motivate our metric as a natural extension to UI that expands the class of environments evaluated with a trade-off of further uncomputability. Our metric is able to capture intelligence of agents in uncomputable environments we care about, such as first-order theorem proving, and also lends itself to providing a notion of intelligence of oracles. We end by proving some properties of the new measure, such as convergence (given certain assumptions about the complexity of uncomputable environments).