Skip navigation
Skip navigation

On the computability of Solomonoff induction and AIXI

Leike, Jan; Hutter, Marcus


How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. We quantify this using the arithmetical hierarchy, and prove upper and in most cases corresponding lower bounds for incomputability. Moreover, we show that AIXI is not limit computable, thus it cannot be approximated using finite computation. However...[Show more]

CollectionsANU Research Publications
Date published: 2018-03-15
Type: Journal article
Source: Theoretical Computer Science
DOI: 10.1016/j.tcs.2017.11.020
Access Rights: Open Access


File Description SizeFormat Image
aixicplexx.pdfAuthor Accepted Manuscript394.21 kBAdobe PDFThumbnail

This item is licensed under a Creative Commons License Creative Commons

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator