[ih] SIP and ENUM

[Tony Finch]

John Levine via Internet-history <internet-history at elists.isoc.org> wrote:
>
> I don't understand this concern. Even the most complicated regex is
> only a pattern that either matches or doesn't, with well understood
> mathematical properties. It doesn't have loops or subroutines, and
> since we have fifty years of experience with regex matching, we know
> how to handle them efficiently.

Well, one of the classic ways to create a system that is accidentally
Turing complete is to combine regular expressions with a rewrite loop.
(Sendmail is a well-known example, but basically any MTA is Turing
complete by the same logic.)

NAPTR records combine regular expressions with a rewrite loop, but they
avoid being Turing complete because the regex rewrite is always applied
to the original input string, not to the output of the previous rewrite.
RFC 2915 says this is because the Turing complete version would be too
confusing, without mentioning that it would also be Turing complete.

Tony.
-- 
f.anthony.n.finch  <dot at dotat.at>  http://dotat.at/
Gibraltar Point to North Foreland: Cyclonic becoming northerly 5 or 6,
decreasing 3 or 4 later. Slight or moderate, becoming smooth or slight later.
Occasional rain or drizzle then showers. Good, occasionally poor at first.