Message Boards Message Boards

Analytical solution for nth application of a rule

Is it possible formalise a general procedure that evaluates the nth application of a rule to any graph? ie the graph equivalent of what the Binet Formula is to the Fibonacci sequence.

Finding an analytical solution to this would greatly reduce the overall computational cost of the project. I have found examples of pairs of certain rules and graphs that have a defined nth term formula, (though they are quite contrived) so perhaps it might not be impossible to find a general procedure.

POSTED BY: Christopher Tan
2 Replies

I think a general procedure would be directly in conflict with the computational irreducibility principle.

Posted 4 years ago

It is possible to compute what you are suggesting (essentially, products of the rule with itself). In fact, we have this prototype function (it's not documented, but there are some examples), which allows you to do that.

The problem, however, is that in general, you would get multiple rules as a result of such a product. Each of the rules would also be typically larger than the original, so it does not help with optimization. And yes, this is a direct consequence of computation irreducibility.

POSTED BY: Max Piskunov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract