3 ms·
I also don't see the relevance of it being TC. I've heard regex is TC. Wouldn't want to write a contract in regex.
by intrasight 10y ago
I also don't see the relevance of it being TC. I've heard regex is TC. Wouldn't want to write a contract in regex.
- wyager 10y ago> I've heard regex is TC. You heard wrong. Regex is specifically not turing complete. It corresponds to the class of machines called DFAs. Above regexes are CFGs, which correspond to pushdown automata. Above CFGs are CSGs, which correspond to linear bounded automata. Above CSGs are unrestricted grammars, which correspond to turing machines. You may be thinking of PCREs, which aren't actually regular expressions, but are sometimes erroneously referred to as such. I don't know if those are turing complete or not.
- SolarNet 10y agoBy definition regular expressions are not Turing complete... There is an ordering relationship between turing machines and regular expressions which explicitly states regular expressions are strictly a subset of turning machines. This is automata theory 101. Ask for a refund from your school. Jesus what has this field come to.