This isn’t quite the same as weighting by minimum description length in the Solomonoff sense, since we care specifically about symmetries which correspond to function calls—i.e. isomorphic subDAGs. We don’t care about graphs which can be generated by a short program but don’t have these sorts of symmetries.
Can you elaborate on this? What would be an example of a graph that can be generated by a short program, but that does not have these sorts of symmetries?
My intuition is that the class of processes your describing is Turing complete, and therefore can simulate any Turing machine, and is thus just another instance of Solomonoff induction with a different MDL constant.
I’ll give an answer via analogy: the digit sequence 123123123123123… is symmetric: the sequence directly contains a copy of itself. The sequence 12345678910111213141516… is not symmetric: it will not repeat and does not contain a copy of itself, although there is a pattern and it could be generated programmatically.
Similarly with DAG symmetries. If we’re producing these DAGs by expanding out programs, then the only infinite patterns we’ll see are symmetries—subDAGs which repeat, corresponding to function blocks. We don’t need to worry about DAGs with strange patterns which could be generated programmatically but can’t just be built by repeating subDAGs.
I’m not sure I get your analogy, but my intuition is that FactorialCode is right regarding Turing completeness / just a different minimum description length constant. Like, I think I can turn a collection ‘programatically generated’ but not self-similar sub-DAG into a structure which has internalised the generative power. For example, perhaps it now consumes and switches on some extra state.
If I can do that, I now have a self-similar building block that counts for our symmetries. There’s some overhead in the translation, hence the different MDL constant.
Can you elaborate on this? What would be an example of a graph that can be generated by a short program, but that does not have these sorts of symmetries?
My intuition is that the class of processes your describing is Turing complete, and therefore can simulate any Turing machine, and is thus just another instance of Solomonoff induction with a different MDL constant.
Edit: Rule 110 would be an example.
Were you summoned by this post accidentally using your true name?
I’ll give an answer via analogy: the digit sequence 123123123123123… is symmetric: the sequence directly contains a copy of itself. The sequence 12345678910111213141516… is not symmetric: it will not repeat and does not contain a copy of itself, although there is a pattern and it could be generated programmatically.
Similarly with DAG symmetries. If we’re producing these DAGs by expanding out programs, then the only infinite patterns we’ll see are symmetries—subDAGs which repeat, corresponding to function blocks. We don’t need to worry about DAGs with strange patterns which could be generated programmatically but can’t just be built by repeating subDAGs.
I’m not sure I get your analogy, but my intuition is that FactorialCode is right regarding Turing completeness / just a different minimum description length constant. Like, I think I can turn a collection ‘programatically generated’ but not self-similar sub-DAG into a structure which has internalised the generative power. For example, perhaps it now consumes and switches on some extra state.
If I can do that, I now have a self-similar building block that counts for our symmetries. There’s some overhead in the translation, hence the different MDL constant.