Skip to main content

Getting Stuck: Writing a Turing Machine Simulator

 

Getting Stuck: Writing a Turing Machine Simulator

This entry in my Getting Stuck series started with what I thought was a fun challenge: write a Turing machine simulator from scratch.

It sounded clean and manageable. After all, how hard could it be? A tape, a head, some states, some rules. By the end, I had written code that ran… and then refused to stop. I had also stumbled into undecidability theorems I’d only read about in textbooks.

This is the story of how I got stuck — and what climbing out looked like.

Step 1: The Innocent Beginning

A Turing machine is described in almost childlike terms:

  • An infinite tape with symbols on it.

  • A head that can move left or right.

  • A finite set of states.

  • A transition function telling the machine what to do next.

So I wrote down the core class in Python:

class TuringMachine:
    def __init__(self, tape, transitions, start_state, accept_state, reject_state):
        self.tape = list(tape)
        self.head = 0
        self.state = start_state
        self.transitions = transitions
        self.accept_state = accept_state
        self.reject_state = reject_state

    def step(self):
        symbol = self.tape[self.head]
        key = (self.state, symbol)
        if key not in self.transitions:
            self.state = self.reject_state
            return
        new_state, write_symbol, move = self.transitions[key]
        self.tape[self.head] = write_symbol
        self.state = new_state
        self.head += -1 if move == "L" else 1

I was optimistic. Next up was testing it on the simplest machine I could think of: recognizing strings of as with even length.

Step 2: First Crash

Transitions for the “even length” checker:

transitions = {
    ("q0", "a"): ("q1", "a", "R"),
    ("q1", "a"): ("q0", "a", "R"),
    ("q0", "_"): ("ACCEPT", "_", "R"),
    ("q1", "_"): ("REJECT", "_", "R"),
}

Running it on "aaaa_":

tm = TuringMachine("aaaa_", transitions, "q0", "ACCEPT", "REJECT")
while tm.state not in ("ACCEPT", "REJECT"):
    tm.step()
print("Result:", tm.state)

Boom.
IndexError: list index out of range.

The head had marched off the right edge of my tape. My machine had fallen into the void.

Step 3: Mistaken Fixes

The obvious fix? Just make the tape longer.

self.tape = list(tape) + ["_"] * 1000

This worked — until I gave it a longer input, and it ran out of blanks again. My tape wasn’t infinite; it was just really wide.

Then I got clever. What if the tape “wrapped around”?

self.head = (self.head + 1) % len(self.tape)

No more index errors! But the logic was broken. The head that was supposed to drift forever to the right instead looped back and scribbled on the start of the tape. Suddenly, my machine was “accepting” inputs it should’ve rejected.

I had “fixed” the bug in a way that destroyed the whole model.

Step 4: The Real Fix

The right way to simulate infinity is… not to. It’s to cheat intelligently.

If the head walks off the left end, insert a blank at the start.
If it walks off the right end, append a blank at the end.

def step(self):
    if self.head < 0:
        self.tape.insert(0, "_")
        self.head = 0
    elif self.head >= len(self.tape):
        self.tape.append("_")

    symbol = self.tape[self.head]
    key = (self.state, symbol)
    if key not in self.transitions:
        self.state = self.reject_state
        return
    new_state, write_symbol, move = self.transitions[key]
    self.tape[self.head] = write_symbol
    self.state = new_state
    self.head += -1 if move == "L" else 1

With this change, the machine finally behaved properly:

  • "aa" → accepted.

  • "aaa" → rejected.

  • "aaaa" → accepted.

I had successfully built an actual Turing machine simulator.

Step 5: Running Into Theoretical Walls

At this point, I was feeling confident. Time to test something bigger: a palindrome recognizer.

But then the simulator… just kept running. And running.

# Contrived infinite loop
transitions = {
    ("q0", "a"): ("q0", "a", "R"),
}

My program hung forever. I was convinced I had a bug — until I remembered a lecture from my theory course.

The halting problem.

It’s not just a story in textbooks. You literally cannot, in general, decide whether a Turing machine will halt on a given input. My simulator wasn’t broken. It was faithfully reproducing one of the deepest truths of CS: sometimes, computation just doesn’t end.

Step 6: Climbing Out

At first, I was frustrated. My “palindrome machine” was hopeless. I considered adding an artificial timeout: “if it runs 10,000 steps, just stop.” That let me keep experimenting, but it wasn’t a real solution.

Eventually, I accepted that this wasn’t a programming bug. It was a fundamental feature of the model. A simulator of Turing machines will always face inputs that lead to infinite loops.

And that’s when it hit me: I hadn’t just built a quirky toy. I had experienced the line between “things we can compute” and “things we cannot.”

Reflection

This round of Getting Stuck was unlike my earlier ones. It wasn’t about fixing a messy bug or optimizing away inefficiency. It was about realizing that getting stuck can sometimes mean reaching the limits of computability itself.

  • I started with the naive assumption that “infinite” just meant “big enough.”

  • I tried wrong fixes that worked mechanically but broke the math.

  • I finally built a working simulator, only to slam into undecidability.

In the end, my code works — but it also reminds me that not every problem is solvable. Sometimes getting stuck is not an accident; it’s a fundamental property of the landscape.


Labels:

Comments

Post a Comment

Popular posts from this blog

Sharp Extremal Bounds for Angular Occupancy (Behind the Curtains)

you can find the full paper here First Attempts, and the Limits of Energy When I first began thinking about angular occupancy, I wasn’t looking for a brand-new problem. I was chasing a theme that has long fascinated me in discrete geometry: how do we measure the geometric richness of a finite set of points? This fascination is not unique to me. Erdős, way back in 1946, posed the distinct distances problem : given n points in the plane, how many distinct distances can they determine? That question alone gave birth to entire decades of work in combinatorial geometry. Later, Fishburn and Füredi asked about distinct angles , while Pach and Sharir studied repeated angles . Each time, the same underlying itch was being scratched: when you place points in the plane, what kinds of diversity can they generate? Why angles, why bins? It was natural to think of angles — after all, distances and directions had already been well studied. But if you go straight for “distinct angles,” you run in...
Post a Comment
Read more

The Art of Goodbye

  The Art of Goodbye: How Relationships End and Why It Matters The friendship had been slowly dissolving for months. What used to be weekly coffee dates became monthly check-ins, then sporadic text messages, then silence. No fight precipitated the ending, no dramatic confrontation or betrayal. It simply... faded. One day you realized you hadn't spoken to someone who was once central to your life, and you weren't sure when the relationship had officially ended or even if it had. This ambiguous loss left you with a peculiar grief – mourning someone still alive, still accessible, but no longer present in your world. This experience is incredibly common yet rarely discussed. While we have cultural scripts for how relationships begin – meet-cutes, first dates, friendship origin stories – we have few models for how they end. We talk extensively about building connections but rarely about gracefully releasing them. This gap in our social understanding leaves many people unprepared ...
1 comment
Read more

Getting Stuck: When Dijkstra Meets Negative Edges

  Getting Stuck: When Dijkstra Meets Negative Edges One of the joys (and pains) of computer science is when you take a tool you know, confidently apply it, and then watch everything break down in surprising ways. This happened to me recently when I decided to revisit shortest path algorithms — specifically, Dijkstra’s algorithm — only to get stuck in a swamp of negative edges. Setting the Scene The problem was classic: Given a directed, weighted graph and a source vertex, find the shortest path to all other vertices. This is the kind of problem that every CS student learns early, usually with Dijkstra’s algorithm. I already knew Dijkstra like an old friend: Keep a priority queue of distances. Always expand the node with the current smallest distance. Relax its edges. Simple, elegant, efficient ( O((V + E) log V) with a binary heap). So when I started coding a graph utility for my project — a tool to analyze transportation networks — I confidently plugged in D...
Post a Comment
Read more