What kind of mathematics do I need to solve for a sequence of operations to get from one state to another?

Question

I'm trying to solve a certain type of engineering problem, but I don't know what kind of math would apply to solving this problem. I'm not asking to solve the problem for me, but I am having trouble searching for the terms online when I don't even know what the math might be called.

An example of the problem would be that I have the state of a few objects (for example whether a few solenoids on a machine are enabled or disabled). Then I have a set of commands I can run. One command might toggle the state of the first two. I might have another command that toggles the state of every other solenoid. A third command might reset all solenoids to their default state.

I want to be able to solve a statement, such as: when there are 4 solenoids and the initial states are ON, OFF, ON, ON, what sequence of commands (from a predefined set of commands I have) do I need to run such that the final state will be ON, OFF, OFF, OFF). (Also is it even possible to get to the desired state?)

When I was in college I took a class on abstract algebra, and I seem to vaguely remember some similar math, but can't quite remember.

(p.s., if anyone can apply more relevant tags, that would be helpful!)

Answer 1

I'm not entirely certain, but it sounds like this might be closest to a Boolean satisfiability problem, and specifically an XOR-satisfiability problem, which is equivalent to solving a system of linear equations mod 2, where each command represents a variable, and each solenoid represents an equation.

Answer 2

What you need is to learn how to do (linear) algebra over the field $\mathbb Z/2 \mathbb Z$.

$\mathbb Z/2 \mathbb Z$ is a number system consisting of two elements: $0$ and $1$. Addition and multiplication work the way you expect them to, except that $1+1=0$. You can even divide (by $1$) and subtract in this system.

Now, you have an array of $n$ "solenoids" (whatever those are), which can be in a state $0$ or $1$. You also have $m$ "buttons", and each button toggles a specific set of solenoids. If we represent the state of a solenoid by a value in $\mathbb Z/2 \mathbb Z$, then pressing a button adds $1$ to the state of each solenoid that it's connected to.

So let's take specific solenoid, and let's say that it's connected to three different buttons (that is, there are three different buttons that toggle it - they may toggle other things as well, but that's not important right now). Note that if you press a button twice, it's as if you didn't press it at all, so we can assume each button is pressed either once or not at all. So let $x$ be the number of times we press the first button, $y$ the second button and $z$ the third. Then, if $a$ is the initial state of the button, the final state is

$$a+x+y+z$$

Where we calculate in the field $\mathbb Z/2 \mathbb Z$. Thus if we want to turn off the solenoid, we must solve

$$x+y+z=-a$$

We have one such equation for each solenoid, and so we end up with a system of linear equations over $\mathbb Z/2 \mathbb Z$ which can be solved by a variety of algorithms.

Start learning about modular arithmetic.