Another concern is that the true hypothesis may be incomputable. There are known definitions of binary sequences which make sense, but which no Turing machine can output. Solomonoff induction would converge to this sequence, but would never predict it exactly.
This statement is simply false. There are a bunch of theorems in machine learning about the class of sequences that an algorithm would converge to predicting (depending on your definition of convergence...is it an algorithm that is eventually right...an algorithm for guessing algorithms that eventually always give the correct answer etc..) but every single one of them is contained in the tiny class of sequences computable in 0′.
To put it another way given any algorithm that guesses at future outputs there is some sequence that simply disagrees with that algorithm at each and every value. Thus any computable process is maximally incorrect on some sequence (indeed is infinitely often wrong on the next n predictions for every n on a dense uncountable set of sequences...say the 1-generics).
However, this is not the end of the story. If you allow your hypothesis to be probabilistic things get much more interesting. However, exactly what it means for induction to ‘work’ (or converge) in such a case is unclear (you can’t get it to settle on a single theory and never revise even if the theory is probabilistic).
This statement is simply false. There are a bunch of theorems in machine learning about the class of sequences that an algorithm would converge to predicting (depending on your definition of convergence...is it an algorithm that is eventually right...an algorithm for guessing algorithms that eventually always give the correct answer etc..) but every single one of them is contained in the tiny class of sequences computable in 0′.
To put it another way given any algorithm that guesses at future outputs there is some sequence that simply disagrees with that algorithm at each and every value. Thus any computable process is maximally incorrect on some sequence (indeed is infinitely often wrong on the next n predictions for every n on a dense uncountable set of sequences...say the 1-generics).
However, this is not the end of the story. If you allow your hypothesis to be probabilistic things get much more interesting. However, exactly what it means for induction to ‘work’ (or converge) in such a case is unclear (you can’t get it to settle on a single theory and never revise even if the theory is probabilistic).