This is a subject that I'm fairly well-read on. Look up Eray Ozkural's work on this.

You have correctly identified that the problem with Solomonoff induction (at least as it's usually formulated) is that representations of programs in terms of binary strings (the Turing machine formalism) isn't very ideal for approximating Solomonoff induction. Circuits and/or neural networks are somewhat better, but still extremely limited because as you try to do more and more complicated computations, your neural networks become exponentially more complicated in structure.

Ideally, you want a representation system that is adaptive - it can use solutions found in previous problem-solving attempts, apply abstraction, and work in a 'higher' representation space. That is, it develops its own 'language' for representing programs at a high level where the search space is correspondingly smaller. This is the basis of the OOPS system (optimally ordered problem solver).

But we can still do better. Instead of using the Turing representation, using stochastic context-sensitive grammars allows a far more compact and easily navigable search space. This is the basis of Ozkural's work, such as http://link.springer.com/chapter/10.1007%2F978-3-319-09274-4_12#page-1