Does the set of all programs form a group that acts on machine state (essentially, i.e. with a few exceptions)?

Question

Since the only thing a computer can do is modify its machine state, and you can always change from one state into another state (there exists such a program) and so each program is invertible; and if all the programs are deterministic, then associativity also makes sense. Two programs are considered equivalent iff they do the same thing to the machine's state, given any starting state.

So do I have the title right or not?

Answer 1

The short answer is that the set of all computer programs can reasonably be made into a monoid, but probably not a group, since not every program has an inverse.

Let's assume that $S$ is the set of all states of the computer, and $P$ is the set of all computer programs. Let's also assume that for every program $a$, that program has an interpretation, written $i[a]$, which is a function $S \to S$ which describes the effect that the program $a$ has when it's executed. Define $i[P]$ as the set of all program interpretations, which is to say, the set $\{ i[a] : a \in P \}$. Notice that $i[P]$ is a subset of the set of all functions $S \to S$.

Presumably, there is a trivial program $0$ which leaves the state of the computer unaffected; the interpretation function $i[0]$ is the identity function. Also, given two programs $a$ and $b$, there is presumably a "composite" program $b \cdot a$ which has the same effect as running $a$ and $b$ in sequence; the interpretation functions satisfy the equation $i[b \cdot a] = i[b] \circ i[a]$. These two facts mean that the set $i[P]$ is in fact a monoid; specifically, it's a submonoid of the monoid of all functions $S \to S$.

However, is $P$ itself a monoid? It depends.

Suppose that our programming language has the property that the empty string is the trivial program $0$, and that given two programs $a$ and $b$, we can simply concatenate them to obtain the composite program $b \cdot a$. In this case, $P$ is a monoid with the empty string as the identity element and string concatenation as the operation. Furthermore, the interpretation functional $i$ is an action of $P$—in other words, the monoid $P$ "works correctly" with respect to the meanings of programs.

However, with most real-world programming languages, such as C#, it's not possible to compose two programs by merely concatenating them. But it is usually possible to define some way of composing two programs. If we're not careful, we'll end up with a definition of program composition which is not associative—given programs $a$, $b$, and $c$, the composite programs $(c \cdot b) \cdot a$ and $c \cdot (b \cdot a)$ will be two different programs that do the same thing. In this case, $P$ fails to be a monoid.

But, by using care and creativity, it should be possible to define program composition in such a way that it is associative, in which case $P$ is once again a monoid.

In general, programs are not invertible, so there is no reasonable way to define $P$ as a group. For example, if the program x = 0; sets the variable x to $0$, then there is no program p such that the program p; x = 0; causes x to remain unchanged, and so the program x = 0; has no inverse.

However, if we consider the set $R$ of all reversible computer programs, we could define a group structure on $R$ in pretty much the same way we defined a monoid structure on $P$.

Answer 2

I'm pretty sure programs form a monoid and inverses don't exist. The problem with inverses is that there may be two input states that result in the same output state for a program, leaving no unique inverse.

Answer 3

I believe the question arises from a few misconceptions on computational models. I'll try to address those.

The question describes a program $p$ as a transition from a single state $x$ to another one $y$. This view does not agree with the common notion of program we use in computer science.

In CS, there is no "absolute" definition of "program". We typically define, on a case by case basis, a programming language as a set of strings (elements of a free, finitely generated monoid), and provide each of such strings with its semantics. This can be done in a plethora of distinct ways. We have small-step operational semantics that describes how a program state repeatedly changes from the beginning to the end of the computation (if there's an end). We have big-step operational semantics, that only relates the start and end states without caring about the intermediate ones. We also have other styles of semantics such as denotational, axiomatic, ... that do not focus so much on program states.

That being said, let us limit to operational semantics. Even in such case, a program does not just map a single state $x$ to a single state $y$. A program can always receive some input from outside, and act accordingly. So, at the very least, the same program can start from multiple initial states $x$ (assuming the input is encoded in some way in the state), and -assuming termination- will reach a potentially distinct state $y$ for each input.

The question then mentions that this is invertible because there is always a program $q$ that can change $y$ back to $x$. While that might be technically correct in many computational models, this depends on a quantification of the variables that makes this result useless in practice.

Indeed, what happens is that for each $x$ and each $y$ there is a program $q$ that changes $y$ back to $x$. That is true only because we can choose $q$ depending on $x$ and $y$. Moreover, that does not imply that there is a program $q$ that can change any end state $y$ to "its own" starting state $x$. The main misconception here is having a program $q$ which is only required to act on a single case, the states $x$ and $y$. This is not a useful view: any notion of "program" must be able to work with many (often infinitely many) cases.

The question then mentions program determinism to claim that computation can be always reversed. Determinism is a fundamental property that simply states "same input, same behaviour", or "same input, same output". In other words, it states that a program behaves like a (partial) function. This however, does not ensure that the function is invertible.

Consider a program that, given a natural number as input, outputs its half, rounded down. There is no general way here to compute the input given the output.

Finally, let me add that in many computational models we do have some way to compose programs, in the same way we can compose functions. This however only forms a monoid, not a group.

To have a group you'd need to restrict the computational model so that it can only compute bijections. Even if this is not the common case in CS, one can still choose to explore this realm. Indeed, as far as I know, that's the aim of research in reversible computation (including its applications to quantum computing).

Answer 4

No. This step in your argument is wrong:

you can always change from one state into another state (there exists such a program) and so each program is invertible

More formally, this says:

• For all states $s_1$,
• for all states $s_2$,
• there exists a program $\color{blue}{q}$ such that $q(s_1) = s_2$.

From this, you can infer that

• For all programs $p$,
• for all start states $\color{red}{s}$,
• there exists a program $\color{blue}{q}$ such that $q(p(s)) = s$.

$$ \forall\,p: \textsf{Prog}. \color{red}{\forall\,s: \textsf{State}}. \color{blue}{\exists\,q: \textsf{Prog}}.q(p(s))=s $$

With some sufficiently restrictive notions of "programs" $\textsf{Prog}$ and "machine states" $\textsf{State}$, this could indeed be forced to be true, but this is not what you want.

What you want instead is that "each program $p$ has an inverse", namely:

• For all programs $p$,
• there exists a program $\color{blue}{q}$ such that
• for all states $\color{red}{s}$, $q(p(s)) = s$.

$$ \forall p: \textsf{Prog}. \color{blue}{\exists q: \textsf{Prog}}. \color{red}{\forall s: \textsf{State}}.q(p(s))=s $$

Again, both formulas, side by side, for easier comparison:

$$ \forall\,p: \textsf{Prog}. \color{red}{\forall\,s: \textsf{State}}. \color{blue}{\exists\,q: \textsf{Prog}}.q(p(s))=s \\ \forall\,p: \textsf{Prog}. \color{blue}{\exists\,q: \textsf{Prog}}. \color{red}{\forall\,s: \textsf{State}}.q(p(s))=s $$

You have swapped the second $\color{red}{\forall}$ and the $\color{blue}{\exists}$:

• $\color{red}{\forall s}-\color{blue}{\exists q}$: The first one is easy (assuming that for each given $s$, you can construct a $q$ which simply overrides the previous state by $s$).
• $\color{blue}{\exists q}-\color{red}{\forall s}$: The second one is impossible (because $p$ might destroy some information, as already said in Oscar Smith's answer).

You can try to construct something like a monoid (submonoid of endomorphism monoid $\textsf{End}(\textsf{State}))$, but you can't get the inverses, so it's not a group.