Regex (at least most implementations) isn't Turing complete, but you can still do a lot of stuff with it and I think most type systems go far beyond regex in ex

Regex (at least most implementations) isn't Turing complete, but you can still do a lot of stuff with it and I think most type systems go far beyond regex in expressive power. Unless you're trying to write quines, you probably don't need Turing completeness.