CoC - A Domain-Theoretic Approach to Approximations of Lower Semi-Computable Semi-Measures

13 April 2026, 12:00, Skaidrite Darius Level 2 - Systems Area
Speaker: Sigfrido D. Ciletti (ANU)

Abstract#

Solomonoff induction represents the uniquely optimal solution to inductive inference, yet it remains fragmented and practically non-constructive. Algorithmic Information Theory (AIT) suffers from a formal bifurcation between finite and infinite sequences, where core primitives—algorithmic probability, Kolmogorov complexity, and Martin-Löf randomness—are defined on incongruent mathematical spaces. Furthermore, while the universal prior M is lower semi-computable, current resource-bounded approximations lack an independent denotational semantics to characterize their convergence without recourse to specific search heuristics. In this talk, we present a unified framework using Domain Theory to resolve these incongruencies. By embedding the set of strings into the Cantor Domain equipped with the Scott topology, we demonstrate that 'infinite' AIT primitives are recovered as natural limit cases of their finite counterparts. We address the 'super-additive gap' in measure theory by investigating a Carathéodory-type extension theorem for semi-valuations on the probabilistic power domain. This approach allows us to model resource-bounded approximations as directed sets whose least upper bound is the ideal Solomonoff valuation. By shifting from operational to denotational proofs, we provide a foundational guarantee of 'bottom-up' convergence, offering a potentially robust metric for evaluating modern AI architectures as approximations of universal induction.
bars search caret-down plus minus arrow-right times