← Back to TILs

DNS is turing complete?

November 1, 2025

I proved DNS is Turing complete last week.

Okay, maybe “proved” is a stretch, I was definitely trying to do something weird with DNS. But here’s the thing: I was reading about Rule 110 cellular automata at home while debugging a weird DNS bug at work and I had this mixture of a thought: “What if DNS responses could compute things?”

Now, hear me out. DNS is supposed to be this boring infrastructure protocol that just maps domain names to IP addresses. But what if we could make it… compute?

The Rule 110 Rabbit Hole

Rule 110 is this deceptively simple cellular automaton that turns out to be Turing complete. That means, theoretically, you could build a computer out of it. All you need is:

  1. A row of cells (0s and 1s)
  2. A simple lookup table
  3. Time (lots of it)

Here’s how it works: each cell looks at itself and its two neighbors, checks a lookup table, and figures out what it should be in the next generation.

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

That’s it. That’s the whole rule. And from this absurdly simple rule, you get Turing completeness. Wild, right?

Let me show you what happens when you start with a single cell and let it evolve:

Gen  0: |                                                    █|
Gen  1: |                                                   ██|
Gen  2: |                                                  ███|
Gen  3: |                                                 ██ █|
Gen  4: |                                                █████|
Gen  5: |                                               ██   █|
Gen  6: |                                              ███  ██|
Gen  7: |                                             ██ █ ███|
Gen  8: |                                            ███████ █|
Gen  9: |                                           ██     ███|
Gen 10: |                                          ███    ██ █|

Beautiful chaos emerging from simple rules. This is why I love computer science.

Wait, What About DNS?

So here’s where it gets fun. DNS packets have this thing called TXT records. They’re meant for arbitrary text data. Most people use them for things like domain verification or SPF records. Boring stuff.

But what if we used them for… computation results?

The architecture is actually pretty straightforward:

(But making this diagram was not, so please appreciate)

┌──────────────┐
│              │
│  DNS Client  │
│              │
└──────┬───────┘
       │
       │ 1. Query: google.com TXT
       │
       ▼
┌──────────────────────────────────────────┐
│                                          │
│           DNS Server (Port 5454)         │
│                                          │
│  ┌────────────────────────────────────┐  │
│  │                                    │  │
│  │  1. Receive DNS query              │  │
│  │  2. Parse domain name              │  │
│  │  3. Hash domain → initial state    │  │
│  │                                    │  │
│  └────────────┬───────────────────────┘  │
│               │                          │
│               ▼                          │
│  ┌────────────────────────────────────┐  │
│  │                                    │  │
│  │      Rule 110 Computation          │  │
│  │                                    │  │
│  │   State: 000100110...              │  │
│  │   Gen 0: █  █  ██                  │  │
│  │   Gen 1: ████ ███                  │  │
│  │   Gen 2: █    █ █                  │  │
│  │   ...                              │  │
│  │                                    │  │
│  └────────────┬───────────────────────┘  │
│               │                          │
│               ▼                          │
│  ┌────────────────────────────────────┐  │
│  │                                    │  │
│  │  4. Build DNS TXT response         │  │
│  │  5. Send back to client            │  │
│  │                                    │  │
│  └────────────────────────────────────┘  │
│                                          │
└──────────────────────────────────────────┘

The flow is:

  1. Client sends a DNS query for any domain
  2. Server hashes the domain name to create an initial state
  3. Server runs Rule 110 for N generations
  4. Server encodes the computation result as a TXT record
  5. Client receives Turing-complete computation in a DNS response

The Implementation

The code ended up being surprisingly clean. Here’s the core of the Rule 110 computation:

RULE_110 = {
    "111": "0", "110": "1", "101": "1", "100": "0",
    "011": "1", "010": "1", "001": "1", "000": "0"
}

def rule110_step(state):
    padded = '0' + state + '0'
    return ''.join(RULE_110[padded[i:i+3]] for i in range(len(state)))

That’s it. The entire Turing-complete computation engine is about 10 lines of Python.

The DNS part is a bit more involved because, well, DNS packets are binary and kind of annoying to work with. But the basic structure is:

# Parse incoming DNS query
domain, transaction_id = parse_query(data)

# Compute Rule 110
computation = compute_rule110(domain, generations=5)

# Send back as TXT record
response = build_response(data, computation)
sock.sendto(response, address)

One tricky bit: DNS TXT records have a 255-byte limit per string, so I had to chunk the output. But that’s just the (boring?) engineering details.

Does It Actually Work?

Oh, it absolutely works. Check this out:

$ dig @localhost -p 5454 google.com TXT +short
"Gen  0:                  ████  █ █     ████████ █                "
"Gen  1:                 ██  █ ███    ██      ███                "
"Gen  2:                ███ ████ █   ███     ██ █                "
"Gen  3:               ██  ██  ███  ██ █    █████                "
"Gen  4:              ███ ███ ██ █ ███████  ██   █                "

Every query triggers a new computation. Different domains produce different initial states (via MD5 hash), which produce different evolutionary patterns.

Is This Actually Useful?

Absolutely not. This is peak “your scientists were so preoccupied with whether they could, they didn’t stop to think if they should” energy.

But here’s why I think it’s cool anyway:

  1. It proves a point: Protocols can be more expressive than their designers intended
  2. It’s just fun: Sometimes the best projects are the ones that make you go “wait, that shouldn’t work”

What’s Next?

Could you build a full computer this way? Theoretically, yes. Rule 110 is Turing complete, which means given enough time and space, it can compute anything computable.

Practically? You’d need:

  • Persistent state across queries (maybe use Redis?)
  • A way to encode programs as initial states
  • Patience (Rule 110 is slow)
  • A really good reason (which you don’t have)
  • Did I say patience? A lot of it?

But the fact that it’s possible is what matters. DNS isn’t just a lookup table. It’s a programmable medium.

Try It Yourself

The code is dead simple—just Python standard library, no dependencies:

# Clone and run
git clone https://github.com/VedWhat/turing-complete-dns
cd turing-complete-dns
python3 dns_rule_110.py

# In another terminal
dig @localhost -p 5454 anything.you.want TXT

Each domain you query will produce a unique computational pattern. Try google.com, github.com, your own name—they all generate different Rule 110 evolutions.

Final Thoughts

This started as a “what if” and turned into a weekend project that I’m weirdly proud of. It’s not going to change how we think about networking. It’s not going to make DNS better (if anything, it makes it worse).

But it’s a reminder that computers are still magical, even the boring parts. DNS has been around since 1983, and we’re still finding weird things to do with it.

Now if you’ll excuse me, I have a sudden urge to see if I can make ICMP Turing complete…

Update: Someone pointed out that technically the protocol isn’t Turing complete—the server is. Fair point. DNS is just the transport mechanism. But “I built a Turing-complete server that speaks DNS” doesn’t have the same ring to it, you know? Makes me look immediately less cool

dns networking
ESC