vedchitnis

I proved DNS is Turing complete last week.

That sentence is doing a suspicious amount of work. “Proved” is generous. “DNS” is not the thing doing the computation in the clean theoretical sense. And if you are a formal methods person, you are already looking for a window to climb out of.

But the experiment was fun enough to deserve the dramatic version:

What if a DNS server could answer TXT queries by evolving a Rule 110 cellular automaton?

The result is part joke, part systems exercise, and part reminder that boring infrastructure gets strange as soon as you let it carry state.

Why Rule 110?

Rule 110 is a one-dimensional cellular automaton. Imagine a row of cells, each either 0 or 1. On every generation, each cell looks at itself and its immediate neighbors. That three-cell pattern determines the next value.

The lookup table is tiny:

Pattern:  111  110  101  100  011  010  001  000
Next:      0    1    1    0    1    1    1    0

That is the whole rule.

From that little table, complex behavior emerges. More importantly, Rule 110 is known to be Turing complete. Given the right initial conditions and enough time, it can simulate computation.

That makes it perfect material for a technical prank. It is simple enough to fit in a blog post, but deep enough that the phrase “Turing complete” is not purely decorative.

Why DNS?

DNS is supposed to be boring in the best way. A client asks a resolver for a name. Eventually, some authoritative server returns records. Most people meet DNS as a mapping from names to IP addresses.

But DNS has TXT records, and TXT records are wonderfully abusable. They are meant to carry arbitrary text: SPF policies, domain verification strings, service metadata, and other little declarations that do not fit elsewhere.

So the idea was:

receive a DNS TXT query
derive or retrieve an automaton state for the queried domain
evolve the state using Rule 110
return the current generation as the TXT response

A query like this:

dig @127.0.0.1 -p 5454 example.com TXT

could return something like this:

"gen=42 state=000111011101110001011..."

Ask again, and the generation advances.

Now DNS is not just resolving a name. It is participating in a tiny computation ritual.

The architecture

The server has four boring parts:

DNS query
  -> parse question
  -> find domain state
  -> evolve Rule 110 generation
  -> return TXT answer

The state can be initialized by hashing the domain name. That makes each queried domain produce a different automaton without requiring setup:

example.com -> hash -> 000100010111...
google.com  -> hash -> 110010100010...

From there, every TXT lookup becomes a clock tick.

The Rule 110 step is straightforward:

left center right -> next
111 -> 0
110 -> 1
101 -> 1
100 -> 0
011 -> 1
010 -> 1
001 -> 1
000 -> 0

For each cell, look at the three-bit neighborhood, read the table, write the next row. Repeat on every query.

Where the claim gets slippery

This is the part where the honest version matters.

Rule 110 is Turing complete. A DNS server that runs Rule 110 internally is not the same as proving the DNS protocol itself is Turing complete. The computation is happening in the authoritative server implementation, and DNS is the request/response carrier.

Still, the joke points at a real systems idea: protocols that look static can become dynamic when their servers are programmable, stateful, and allowed to encode computation in responses.

DNS has caching. DNS has retries. DNS has resolvers between the client and the authoritative server. DNS has record-size limits and transport differences between UDP and TCP. All of those details matter if you try to treat it like a computation substrate.

For example, caching is hilarious here. If a resolver caches the TXT response, repeated queries might not advance the automaton from the client’s point of view. The “computer” appears frozen because DNS is doing its actual job.

The fix is to use low TTLs or unique query names, but that also makes the system more obviously a stunt.

Why this was worth building anyway

The value was not in making a practical computer out of DNS. Please do not do that.

The value was in taking a familiar protocol and asking what its boundaries feel like when pushed:

What does state mean in a request/response protocol?
How do caches change the behavior of dynamic answers?
Where does computation live: client, protocol, or server?
How much weirdness can fit inside a TXT record?

Those questions are useful even when the project is silly.

The best technical experiments often start as jokes because jokes give you permission to ignore whether something is useful long enough to discover whether it is interesting.

So, is DNS Turing complete?

No, not in the clean mathematical way that sentence wants to imply.

But can you build a DNS server that exposes the evolution of a Turing-complete cellular automaton through TXT records?

Yes.

And when you do, DNS stops feeling like a phonebook for a minute and starts feeling like a tiny, badly-advised display for computation.