Computers are confusing. Sure, using a computer for basic needs feels easy to many of us (especially those of us who have grown up using computers), but understanding how they actually work is a different beast entirely. This is even more true for those of us who call ourselves programmers. Every day we must go beyond web browsers and the Downloads folder and dive into the depths of computer logic to make sure everyone else gets the pattern of lights that they want. The problem is, in order to do this we have to learn to think like a computer. This seems to work fairly well for some people, (looking at you Donald Knuth) but for most of us speaking Human is hard enough, let alone understanding the mindset of a mindless rectangle of lights! And yet, part of being a clean, professional coder is understanding how and why a computer does what it does.
In this series of blog posts we will be delving into the fascinating world of Automata Theory from the viewpoint of mere mortals. This means that we will be avoiding sentences like:
“δ is the transition function, that is, δ: Q × Σ → Q”
“Turing machines with automata homomorphisms defining the arrows between automata”.
So if you thrive on technical definitions and theoretical expositions, this is probably not the series for you. If, however, you are a human who just wants to understand where computers come from and the concepts upon which they are built, then you are in the right place.
Before we really dive into the different types of automata there is a very important question we have to answer. What the heck is an automata? You can find detailed, mathematical descriptions online, but when it really comes down to it, an automata is really just a machine that changes its “state” based on the instructions you give it. Now, you may be thinking that this is a broad explanation that can be applied to many things that are not computers, and you would be correct! In fact, that is one reason automata theory is so cool, is that it goes far beyond computers. This is something we will likely discuss in another blog post though. In the meantime, just know that when we say “automata” we simply mean “something that takes instructions and changes its state accordingly”.