the DAG consists of an infinite sequence of copies of the same subcircuit.
If it’s infinite then the program doesn’t terminate. (In theory this may be the case if n is a non-negative integer.)
Ideally, we’d gain enough information to avoid needing to search over all possible programs.
Over all shorter possible programs.
(In principle, we could shoehorn this whole thing into traditional Solomonoff Induction by treating information about the internal DAG structure as normal old data, but that doesn’t give us a good way to extract the learned DAG structure.)
Sounds like SI is being treated as a black box.
We don’t care about graphs which can be generated by a short program but don’t have these sorts of symmetries.
Why do we like programs which use recursion instead of iteration?
The non-termination point is a bit subtle. If you look at the example in the OP, the causal diagram itself is infinite, but as long as we pass in a positive integer the output value won’t actually depend on the whole circuit. One of the conditional nodes will recognize the base case, and ignore whatever’s going on in the rest of the circuit below it. So the program can terminate even if the DAG is infinite. (Equivalent conceptualization: imagine running a lazy evaluator on the infinite DAG.)
That said, DAGs with symmetry certainly can represent computations which do not halt. This is a feature, not a bug: there are in fact computations which do not halt, and we can observe their physical behavior mid-computation. If we want to think about e.g. what my processor is doing when running an infinite loop, then we need a computational model which can represent that sort of thing, rather than just talking about input/output behavior.
If it’s infinite then the program doesn’t terminate. (In theory this may be the case if n is a non-negative integer.)
Over all shorter possible programs.
Sounds like SI is being treated as a black box.
Why do we like programs which use recursion instead of iteration?
The non-termination point is a bit subtle. If you look at the example in the OP, the causal diagram itself is infinite, but as long as we pass in a positive integer the output value won’t actually depend on the whole circuit. One of the conditional nodes will recognize the base case, and ignore whatever’s going on in the rest of the circuit below it. So the program can terminate even if the DAG is infinite. (Equivalent conceptualization: imagine running a lazy evaluator on the infinite DAG.)
That said, DAGs with symmetry certainly can represent computations which do not halt. This is a feature, not a bug: there are in fact computations which do not halt, and we can observe their physical behavior mid-computation. If we want to think about e.g. what my processor is doing when running an infinite loop, then we need a computational model which can represent that sort of thing, rather than just talking about input/output behavior.