On Tue, 11 May 2004, wayne wrote:
"Hallam-Baker, Phillip" <pbaker(_at_)verisign(_dot_)com> writes:
SPF macros are on the verge of being Turing complete.
I've pondered this before and I'm pretty sure that SPF macros are not
Turing complete.
Yes, but as Phill says they are very close to being so. I was looking at
the spec from this point of view last night. I posted to the SPF list:
I thought that (in the absence of the "processing limits" section in the
specification) SPF might be Turing complete. It supports general-purpose
recursion, it has conditional constructs, and it allows the argument to
the recursive call to be altered programmatically. However I haven't yet
managed to work out how to write a conditional that does anything useful.
It turns out that conditionals are not the problem: the exists mechanism
combined with wildcard DNS records is enough. The crucial limitation is in
the macro language, which is only slightly too weak.
Here's an outline of how to make something like a Turing machine using SPF.
The <current-domain> is used to model both the memory of the machine and
its current state, e.g. mem-1.mem-2...mem2.mem1.mem0.state.example.com.
A Turing machine's state transition table is keyed on the contents of the
current memory location (mem0) and the current state. This can be
expressed in the DNS as *.mem0.state.example.com. TXT "v=spf1 ...".
The problem is then to express in the SPF record how to adjust the memory
and the state before redirecting to the next query, or using an exists
query to terminate with success or failure. The DIGIT transformer allows
you to select a specific number of components from the domain, but there
is nothing in the macro language that allows you to select everything
except a certain number of components from the domain.
*NOTE* that even if SPF were Turing complete, its computational ability is
seriously limited by (1) the limited space available in a domain name, and
(2) the processing limits in section 6.2 of the spec.
I also observe that any configuration system flexible enough to be useful
in all the weird and wonderful email setups out there is likely to be
Turing complete; this has been demonstrated for Sendmail and Exim, and is
probably the case for Postfix.
--
Tony Finch <dot(_at_)dotat(_dot_)at> http://dotat.at/