Thanks. This looks helpful.
if there's some set S of computer programs, and the algorithm A solves the halting problem of S, then A + a small amount of code predicts all sequences generated by programs in S.
Method: Go through S in some order. Skip over each program that doesn't halt. Skip over each program when it's falsified by the data. Stop when you reach a program that fits the data, and use its programs until its falsified, at which point you move on to the next program...
Humans are computable. There exists a set of programs that humans cannot predict and a (strongly related) se...
Does anyone happen to know the Komogorov complexity (in some suitable, standard UTM -- or, failing that, in lines of Python or something) of computable approximations of AIXI?
I'm writing a paper on how simple or complicated intelligence is, and what implications that has for AI forecasting. In that context: adopt Shane Legg's measure of intelligence (i.e., let "intelligence" measure a system's average goal-achievement across the different "universe" programs that might be causing it to win or not win reward at each time step, weighted according to the universe program's simplicity).
Let k(x, y) denote the Kolmogorov complexity of the shortest program that attains an intelligence of at least x, when allowed an amount y of computation (i.e., of steps it gets to run our canonical UTM). Then, granting certain caveats, AIXI and approximations thereto tell us that the limit as y approaches infinity of k(x,y) is pretty small for any computably attainable value of x. (Right?)
What I'd like is to stick an actual number, or at least an upper bound, on "pretty small".
If someone could help me out, I'd be much obliged.