This post is a continuation of my last post on The Problem of Tag where I introduced a marble machine called a tag system, and the possible behaviors they can have, namely halting, looping, and diverging. I also talked about the problem of tag, which asks whether a particular tag system operating on a particular starting sequence eventually halts, loops, or diverges. I had also alluded to the fact that tag systems are Turing complete, which is a really important “no-go” theorem when discussing the problem of tag – in particular, it means that there is no fully general solution to the problem. That is, there’s no algorithm that always runs in a finite amount of time that correctly decides which behavior a particular tag system has on a particular string. I’m not going to actually prove this result here, but considering a very naive approach gives some intuition of why this might be true. Consider an algorithm that simulates the running of the tag system:

Sometime last year, I was reading up on a longstanding open math problem that turns out to have a really deep connection with computability theory [1]. For the unfamiliar reader, this is a corner of theoretical computer science that deals with “math computers” — basically, defining mathematical objects that can do computations, and proving mathematical theorems about them. These math computers are more formally called models of computation, and there are some really common ones like state machines and context free grammars that every programmer probably encounters at some point in their career. I’m probably biased though, since I’m a compiler engineer during standard working hours, so these are kind of my bread and butter.

Lately, I’ve been reminiscing about the physics simulations I used to make back in the day. A lot of them were kind of crude, but I’m older and hopefully a bit wiser now, so hopefully I can do it a bit better this time around. Revisiting my old nerdy projects take me back to when I was first grappling with a lot of ideas that would come up over and over again in my education — I’ve heard it said that studying physics is learning a series of progressively smaller lies, and true to form by the time I finished my undergrad physics major I’d studied the same sorts of systems a bunch of times in progressively greater detail and with progressively fancier math. One such system is a gas in a box.

I recently read a fun paper Reed Solomon Codes over the Circle Group that uses circle groups to perform an important kind of error correcting code in finite fields where it’s otherwise difficult. If that sounds like gibberish to you, be not afeard! That’s not really what I’m here to talk about! While quite tangential to the contents of the paper, I was intrigued by the idea of translating circle groups into the context of finite fields, and wondered if there was a good way to understand these groups spatially, given how weird finite fields tend to be. Hence the title of the blog post!