Pattern matching and replacing can be Turing Complete, from sed to rewriting languages.

So it's just a matter of combinatorics.

https://wiki.xxiivv.com/site/rewriting.html