Robot Firing Squad State Machine Synchronisation Problem - Python 3

Today we look at the 1957 Robot Firing Squad Synchronisation problem by John Myhill. This problem is about cellular automation, and state machines, and has applications in modern computing even if we don't use State Machines any more.

To solve this, I used a state machine simulator in Python, as well as animation utilising pygame. All the source code, as well as the solution (written in BAMScriptv1), is available at the GitHub site: https://github.com/Invalid-Entry/FiringSquadSynchronisation

You can also find a full copy of the notes and strategies at the invalid entry blog: https://invalidentry.engineer/blog/death-army-robot-firing-squad/

In the past week, after I had been tackling this problem, I've had two distinct conversations, the first was with another lead developer who was bemoaning the fact that young developers are trying to solve problems that were solved before. The second was with the father of a computing student, who was complaining that he wasn't allowed to use cool frameworks for his project, but instead was frustrated that he was being taught things from 30 years ago.

The coincidence that I happened to be tackling a computer science problem from 1957 was not lost upon me, and that I am appreciating the solution has applications in modern-day computing. This problem and my attempt at a solution as presented here have impacts onto an unknown size 'hive' type automation.

However, I don't know why mathematicians have such dark backgrounds to their puzzles. It's always "you've been imprisoned on a mountain lair, where you have to guess the colour of your hat before you'll be released, but you can only see the other prisoners feet and have one guess per day". Anyways, it's 1957, and mathematician John Myhill is proposing a problem about robot firing squads.


State machines are relatively easy to implement using basic logic. If we use binary inputs (and especially if we're flexible on the memory-value of the state to take advantage of Karnaugh maps etc), we can implement state machines using only sets of AND/OR gates.

And why then did they die out? This is because of technology - even where we would use a state machine, it is cheaper and more effective to use something else like an FPGA or a microprocessor. Microprocessors are mass-produced, and therefore a general-purpose embedded computer is cheaper and provides more functionality (and the ability to change) than dedicated electronics of a State Machine. Even systems such a Power Logic Controllers using Ladder Programming which are great for implementing State Machines on are just microprocessors under the hood providing an interpreter on the top of it.

However states are super helpful in modern programming - for instance, in most of my web applications, I have an object called User. This user has a general state attached to it, which defines the functionality available.