# Memoryless Systems Generate the Class of all Discrete Systems

Authors: Erwan Beurier; Dominique Pastor; David I. Spivak
Journal: International Journal of Mathematics and Mathematical Sciences
 (2019)

---

## Abstract

Automata are machines, which receive inputs, accordingly update their internal state, and produce output, and are a common abstraction for the basic building blocks used in engineering and science to describe and design complex systems. These arbitrarily simple machines can be wired together—so that the output of one is passed to another as its input—to form more complex machines. Indeed, both modern computers and biological systems can be described in this way, as assemblies of transistors or assemblies of simple cells. The complexity is in the network, i.e., the connection patterns between simple machines. The main result of this paper is to show that the range of simplicity for parts as compared to the complexity for wholes is in some sense complete: the most complex automaton can be obtained by wiring together direct-output memoryless components. The model we use—discrete-time automata sending each other messages from a fixed set of possibilities—is certainly more appropriate for computer systems than for biological systems. However, the result leads one to wonder what might be the simplest sort of machines, broadly construed, that can be assembled to produce the behaviour found in biological systems, including the brain.


---

## Body

## 1. Introduction

Automata represent systems that receive inputs, alter their internal states, and produce outputs. The state set of the automaton is to be interpreted as the set of all potential memories or storable experiences. In automata theory, the state set is typically finite. In this case, one can view this memory capacity as limited. On the contrary, when the memory of the automaton is not assumed to be limited (human brain), or its capacity can always be extended (RAM-machines or Turing machines as models of computers in computation theory), the automaton should have an infinite state set.In the theory of dynamical systems, we use a generalisation of automata in which the size of the state space is not restricted to finiteness, or even to countability. Dynamical systems with the behaviour of an automaton, that is, taking inputs in discrete time, are called discrete systems. The state space of such a system acts as a sort of memory of the inputs. Each input influences the current state of the automaton, and the current state is the result of the system’s own form—how it deals with inputs—together with the system’s history.One can imagine a dynamical system whose state space is that of all possible input-histories; a new input simply appends to the existing history to become a new history. On the contrary, one can imagine the “opposite” kind of system: one that completely forgets the previous inputs. These systems are referred to as “simple reflex” in ([1], p. 49), reactive, or memoryless in this paper. The transitions of these automata depend only on the input, as no experience is stored. The system decides according to the current perception of the world, rather than current perception together with past perception. In fact, these memoryless systems could act by making a single distinction in the input—a yes/no Boolean response—and nothing more; we call these Boolean reactive systems.In this paper, we will study the links between systems that have memory and those that do not. More precisely, we prove that systems with memory can be simulated by wiring together systems without memory. Our result provides a theoretical framework that supports artificial neural network approaches. Memory is carried by connections, and not only by individuals, within a compositional hierarchy of parts. In particular, feedback generates memory. This result is already known by electronicians and computer scientists (transistors), but this article formally proves and generalises this intuitive result to any kind of automaton in discrete time, which takes any kind of inputs and returns any kind of outputs. As a special case, when the automata are Boolean (which can compare to transistors), we generate the class of finite automata (which can compare to computers).This article lies between two fields of mathematics: category theory and dynamical systems. Regarding category theory, we need no more than the basic definitions of categories, functors, natural transformations, (symmetric) monoidal categories, and monoidal functors. Regarding dynamical systems from a category-theoretic point of view, Section2 recalls the notions of C-typed finite sets, C-boxes, wiring diagrams, and discrete systems inside a C-box, with reference to [2].In Section3, we introduce discrete systems and a specific mapping that will serve our purposes (Section 3.1). We then introduce two equivalence relations between discrete systems. Both are bigger than the usual bisimulation used in automata theory (in the sense of set inclusion). One corresponds to an external point of view; two systems are equivalent if they transform input streams into output streams in the same way (Section 3.2). The other relation corresponds to an internal point of view: two systems are equivalent if they have “the same structure” (in a sense that is defined in Section 3.3). We prove that these are just two perspectives on the same relation.This equivalence relations plays a crucial role in the two results of Section4. First, we show that any discrete system is equivalent to some wiring together of memoryless systems (Section 4.2). Second, we show that any discrete system with a finite state set is equivalent to a combination of finitely many Boolean reactive systems (Section 4.3).


### 1.1. Notation

In this article, we will use the following notation.(i)
Letℕ denote the set of all natural numbers, ℕ≔0,1,2,….(ii)
By default, the variablen will refer to a natural number: n∈ℕ. We will also see the integers n as their set-theoretic counterparts, that is, 0=∅, and n=0,1,…,n−1; in that context, i∈n simply means i∈0,…,n−1. Note that the set n contains exactly n elements and this is what really matters in this notation.(iii)
When the size of a sequencex0,x1,…,xn−1 does not matter, it will be denoted x¯, which makes it easier to write and read. If each xi is an element of the same set X, then we will write x¯∈X, instead of defining an n=lengthx¯ and writing x¯∈Xn. If xi∈Xi for possibly different Xi values, and if there exists a compact notation X^ for X0×X1×⋯×Xn−1, then we will write x¯∈X^ too.(iv)
Sets is the usual category of sets.


## 1.1. Notation

In this article, we will use the following notation.(i)
Letℕ denote the set of all natural numbers, ℕ≔0,1,2,….(ii)
By default, the variablen will refer to a natural number: n∈ℕ. We will also see the integers n as their set-theoretic counterparts, that is, 0=∅, and n=0,1,…,n−1; in that context, i∈n simply means i∈0,…,n−1. Note that the set n contains exactly n elements and this is what really matters in this notation.(iii)
When the size of a sequencex0,x1,…,xn−1 does not matter, it will be denoted x¯, which makes it easier to write and read. If each xi is an element of the same set X, then we will write x¯∈X, instead of defining an n=lengthx¯ and writing x¯∈Xn. If xi∈Xi for possibly different Xi values, and if there exists a compact notation X^ for X0×X1×⋯×Xn−1, then we will write x¯∈X^ too.(iv)
Sets is the usual category of sets.


## 2. Boxes and Wiring Diagrams

In this section, we will present the background necessary for the understanding of this paper, namely, that of dynamical systems from a categorical point of view. It will be reduced to the absolute minimum used in this article. For more background on monoidal categories and functors, refer [3] and [4]. Our approach is different from the one in [5]. The dynamical systems presented here are defined as a generalisation of automata whose input and output spaces are predetermined. We will define a category of lists, a category of boxes, and diverse operations on them.In this section,C will be any category with finite products, that is: for any finite sequence Aii∈n∈C, the product ∏i∈nAi always exists (typically Sets). Most of the following notions were already defined in [2]; we only recall them without proving their properties. Examples can be found in the longer version of this article [6].


### 2.1. The Category of Typed Finite Sets

Before defining proper boxes, we need to define the notion of input and output ports. These will eventually be the sides of our boxes.Definition 1 (category ofC-typed finite sets [2]).
The categoryTFSC of C-typed finite sets is defined as follows:Objects: an object is any pairP,τ such that P is a finite set and τ:P⟶ObC is a functionMorphisms: a morphism fromP,τ to P′,τ′ is a function γ:P⟶P′ such that τ=τ′∘γIdentities: the identity morphism onP,τ is the identity function of the set PComposition: the composition of morphisms is the usual composition of functions
An object inTFSC is called a C-typed finite set; a morphism in TFSC is called a C-typed function.
We can rewrite aC-typed finite set P,τ as the finite sequence τp0,…,τpn−1, where P=p0,…,pn−1. A C-typed finite set is simply a list of objects in C, indexed by a finite set P. If C=Sets, a Sets-typed finite set is a list of sets.
AC-typed function γ:P,τ⟶P′,τ′ can be then seen as a means to obtain the former list τp0,…,τpn−1 from the latter list τ′p0,…,τ′pn−1, by reordering, duplicating, or even ignoring its elements. As τ=τ′∘γ, the list τp0,…,τpn−1 can be rewritten as τ′γp0,…,τ′γpn−1. Beware of the inversion: γ goes from P,τ to P′,τ′ and we see it as a transformation of the list P′,τ′ into the list P,τ.Definition 2 (sum of typed finite sets [2]).
LetP0,τ0,P1,τ1∈TFSC be two C-typed finite sets.
We define their sum byP0,τ0+P1,τ1=P0+P1,τ0+τ1 as the usual disjoint union of sets P0+P1 and τ0+τ1 as τi on Pi for i∈2.Definition 3 (sum of typed functions [2]).
Letγi:Pi,τi⟶Pi′,τi′i∈2 be two C-typed functions.
We define their sum as theC-typed function γ0+γ1:P0,τ0+P1,τ1⟶P0′,τ0′+P1′,τ1′ such that ∀x∈P0+P1, γ0+γ1x=γix if x∈Pii∈2.
We can view the sumP,τ+P′,τ′ as the concatenation of the lists τp0,…,τpn and τ′p0′,…,τ′pn′′, that is, the list τp0,…,τpn,τ′p0′,…,τ′pn′′ and the sum of C-typed functions as a action on each part of the concatenated list.Proposition 1.
The categoryTFSC has the following properties:(i)
The sum ofC-typed finite sets is a coproduct.(ii)
There is only one C-typed finite set P,τ, where P=∅. We denote it by 0.(iii)
TFSC has a symmetric monoidal structure for the sum +, with 0 as the unit.Proof.
Refer to [2].


### 2.2. Dependent Products

In this subsection, we define the dependent product functor. If aC-typed finite set can be viewed as a list of objects of C, then the dependent product of this list is simply the product of its elements.Definition 4 (dependent product [2]).
We define the dependent product as the functor−^:TFSCop⟶C with the following actions:Action on objects:P,τ^=∏p∈PτpAction on morphisms: ifγ:P,τ⟶P′,τ′, then γ^:P′,τ′^⟶P,τ^ is defined as the function γ^:∏p′∈P′τ′p′⟶∏p∈Pτp such that ∀ap′p′∈P′∈P′,τ′^ and γ^ap′p′∈P′=aγpp∈P.
The interpretation of the dependent product is actually quite straightforward: the dependent product of aC-typed finite set, viewed as a list, is the product of the elements of the list in the same order as they appear in the list. The dependent product is thus a functor that packages the usual operations of diagonal A⟶A×A, projection A×B⟶A, and swapping A×B⟶B×A.
We remind thatC has finite products; as a consequence, the dependent product always exists.Proposition 2.
There is a natural isomorphismP0,τ0+P1,τ1^≅P0,τ0^×P1,τ1^; in other words, the dependent product functor sends coproducts in TFSC to products in C.Proof.
Refer to [2].This property is also quite intuitive: if one views the coproduct inTFSC as the concatenation of lists and the dependent product as the product of the elements of the list, then the dependent product of the concatenation of two lists is the product of the dependent products of each list.


### 2.3. The Category of Boxes and Wiring Diagrams

The categoryTFSC is not the main purpose of this article; however, its properties will be useful for the rest of this article.In the following, by abuse of notation, we will writeX∈TFSC for X,τ and X^ for X,τ^.Definition 5 (C-box [2]).
We callC-box any pair X=Xin,Xout∈TFSC×TFSC.AC-box is a pair of C-typed finite sets Xin,Xout, where Xin represents the list of input ports and Xout represents the list of outputs ports.Definition 6 (wiring diagram [2]).
LetX=Xin,Xout and Y=Yin,Yout be C-boxes.A wiring diagramφ:X⟶Y is a pair of C-typed functions φin,φout such that (i) φin:Xin⟶Yin+Xout and (ii) φout:Yout⟶Xout.TheC-typed function φin tells what feeds the input ports of the box X: each input port of X is either connected to an input port of Y or to an output port of X (in case of feedback); the C-typed function φout tells what feeds the output ports of Y: each output port of Y is connected to some output port of X.We can now compose the wiring diagrams:Definition 7 (composition of wiring diagrams [2]).
Letφ:X⟶Y and ψ:Y⟶Z be two wiring diagrams. We define their composition, denoted ψ∘ϕ, as the pair ψ∘ϕin,ψ∘ϕout, where ψ∘ϕin is defined such that the following diagram commutes:(1)and ψ∘ϕout is defined such that the following diagram commutes:(2)Definition 8 (category ofC-boxes and wiring diagrams [2]).
The categoryWC of C-boxes and wiring diagrams is defined as follows:Objects: an object inWC is a C-boxMorphisms: a morphism between twoC-boxes X and Y is a wiring diagram ϕ:X⟶YIdentities: an identity morphism onX is the identity wiring diagramComposition: the composition of wiring diagrams is the composition defined in Definition 7


### 2.4. Monoidal Structure of the Category of Boxes

The categoryWC has a monoidal structure for the parallel composition of boxes that corresponds to the intuitive idea of parallelising boxes.Definition 9 (parallel composition of boxes [2]).
LetX=Xin,Xout and Y=Yin,Yout be two C-boxes.The parallel composition, or sum, ofX and Y, denoted as X⊞Y, is the box X⊞Y=Xin+Yin,Xout+Yout, where + is the sum of C-typed finite sets (cf. Definition 2).The parallel composition of twoC-boxes summarises to the concatenation of both input ports and both output ports.Definition 10 (parallel composition of wiring diagrams [2]).
Letφ:X⟶Y=φin,φout and ψ:Y⟶Z=ψin,ψout be two wiring diagrams.The parallel composition, or sum, ofφ and ψ, denoted as φ⊞ψ, is the wiring diagram φ⊞ψ=φin+ψin,φout+ψout, where + is the sum of C-typed functions (cf. Definition 3).Proposition 3.
The categoryWC has the following properties:(i)
The closed box □, defined as □=0,0, where 0 is the C-typed finite set ∅,∅⟶C defined in Proposition 2.4 is the unit for the sum of boxes ⊞.(ii)
WC has a symmetric monoidal structure for the sum of boxes ⊞, with □ as the unit.Proof.
Refer to [2].


### 2.5. Dependent Product of Boxes

The aim of this section is to extend the notion of dependent product (Definition 4) toC-boxes and wiring diagrams.Definition 11 (dependent product of aC-box [2]).
The dependent productX^ of the C-box X=Xin,Xout is the pair X^=Xin^,Xout^.Remark 1.
The dependent product ofX0⊞X1 is X0⊞X1^=X0in^×X1in^,X0out^×X1out^.Definition 12 (dependent product of wiring diagrams [2]).
The dependent productX^ of the wiring diagram φ:X⟶Y is the pair φ^=φin^,φout^.Remark 2.
The dependent productφ0⊞φ1 is φ0⊞φ1^=φ0in^×φ1in^,φ0out^×φ1out^.Proposition 4.
Letφ:X⟶Y and ψ:Y⟶Z. The dependent product of ψ∘φ is the pair ψ∘φ^=ψ∘φin^,ψ∘φout^, where (i) ψ∘φin^x,z=φin^ψin^z,φout^x,x and (ii) ψ∘φout^x=ψout^φout^x.Proof.
Refer [2].Remark 3.
The dependent product ofC-boxes and wiring diagrams could be described in terms of monoidal functors; however, the codomain of this functor is not C×C as expected, but a category that has the same objects (pairs of objects A,B of C) but whose morphisms are pairs of morphisms fin^,fout^:A0,B0⟶A1,B1 such that fin^ is the morphism fin^:A1×B0⟶A0 in C and fout^ is the morphism fout^:B0⟶B1 in C. The composition law is the one given in Proposition 4.Until now, we have only defined a category ofC-boxes, with interesting properties. These C-boxes are exactly as their name suggests: empty boxes. The extension of the dependent product to C-boxes is a necessary step in order to define the “inhabitants” of C-boxes.


## 2.1. The Category of Typed Finite Sets

Before defining proper boxes, we need to define the notion of input and output ports. These will eventually be the sides of our boxes.Definition 1 (category ofC-typed finite sets [2]).
The categoryTFSC of C-typed finite sets is defined as follows:Objects: an object is any pairP,τ such that P is a finite set and τ:P⟶ObC is a functionMorphisms: a morphism fromP,τ to P′,τ′ is a function γ:P⟶P′ such that τ=τ′∘γIdentities: the identity morphism onP,τ is the identity function of the set PComposition: the composition of morphisms is the usual composition of functions
An object inTFSC is called a C-typed finite set; a morphism in TFSC is called a C-typed function.
We can rewrite aC-typed finite set P,τ as the finite sequence τp0,…,τpn−1, where P=p0,…,pn−1. A C-typed finite set is simply a list of objects in C, indexed by a finite set P. If C=Sets, a Sets-typed finite set is a list of sets.
AC-typed function γ:P,τ⟶P′,τ′ can be then seen as a means to obtain the former list τp0,…,τpn−1 from the latter list τ′p0,…,τ′pn−1, by reordering, duplicating, or even ignoring its elements. As τ=τ′∘γ, the list τp0,…,τpn−1 can be rewritten as τ′γp0,…,τ′γpn−1. Beware of the inversion: γ goes from P,τ to P′,τ′ and we see it as a transformation of the list P′,τ′ into the list P,τ.Definition 2 (sum of typed finite sets [2]).
LetP0,τ0,P1,τ1∈TFSC be two C-typed finite sets.
We define their sum byP0,τ0+P1,τ1=P0+P1,τ0+τ1 as the usual disjoint union of sets P0+P1 and τ0+τ1 as τi on Pi for i∈2.Definition 3 (sum of typed functions [2]).
Letγi:Pi,τi⟶Pi′,τi′i∈2 be two C-typed functions.
We define their sum as theC-typed function γ0+γ1:P0,τ0+P1,τ1⟶P0′,τ0′+P1′,τ1′ such that ∀x∈P0+P1, γ0+γ1x=γix if x∈Pii∈2.
We can view the sumP,τ+P′,τ′ as the concatenation of the lists τp0,…,τpn and τ′p0′,…,τ′pn′′, that is, the list τp0,…,τpn,τ′p0′,…,τ′pn′′ and the sum of C-typed functions as a action on each part of the concatenated list.Proposition 1.
The categoryTFSC has the following properties:(i)
The sum ofC-typed finite sets is a coproduct.(ii)
There is only one C-typed finite set P,τ, where P=∅. We denote it by 0.(iii)
TFSC has a symmetric monoidal structure for the sum +, with 0 as the unit.Proof.
Refer to [2].


## 2.2. Dependent Products

In this subsection, we define the dependent product functor. If aC-typed finite set can be viewed as a list of objects of C, then the dependent product of this list is simply the product of its elements.Definition 4 (dependent product [2]).
We define the dependent product as the functor−^:TFSCop⟶C with the following actions:Action on objects:P,τ^=∏p∈PτpAction on morphisms: ifγ:P,τ⟶P′,τ′, then γ^:P′,τ′^⟶P,τ^ is defined as the function γ^:∏p′∈P′τ′p′⟶∏p∈Pτp such that ∀ap′p′∈P′∈P′,τ′^ and γ^ap′p′∈P′=aγpp∈P.
The interpretation of the dependent product is actually quite straightforward: the dependent product of aC-typed finite set, viewed as a list, is the product of the elements of the list in the same order as they appear in the list. The dependent product is thus a functor that packages the usual operations of diagonal A⟶A×A, projection A×B⟶A, and swapping A×B⟶B×A.
We remind thatC has finite products; as a consequence, the dependent product always exists.Proposition 2.
There is a natural isomorphismP0,τ0+P1,τ1^≅P0,τ0^×P1,τ1^; in other words, the dependent product functor sends coproducts in TFSC to products in C.Proof.
Refer to [2].This property is also quite intuitive: if one views the coproduct inTFSC as the concatenation of lists and the dependent product as the product of the elements of the list, then the dependent product of the concatenation of two lists is the product of the dependent products of each list.


## 2.3. The Category of Boxes and Wiring Diagrams

The categoryTFSC is not the main purpose of this article; however, its properties will be useful for the rest of this article.In the following, by abuse of notation, we will writeX∈TFSC for X,τ and X^ for X,τ^.Definition 5 (C-box [2]).
We callC-box any pair X=Xin,Xout∈TFSC×TFSC.AC-box is a pair of C-typed finite sets Xin,Xout, where Xin represents the list of input ports and Xout represents the list of outputs ports.Definition 6 (wiring diagram [2]).
LetX=Xin,Xout and Y=Yin,Yout be C-boxes.A wiring diagramφ:X⟶Y is a pair of C-typed functions φin,φout such that (i) φin:Xin⟶Yin+Xout and (ii) φout:Yout⟶Xout.TheC-typed function φin tells what feeds the input ports of the box X: each input port of X is either connected to an input port of Y or to an output port of X (in case of feedback); the C-typed function φout tells what feeds the output ports of Y: each output port of Y is connected to some output port of X.We can now compose the wiring diagrams:Definition 7 (composition of wiring diagrams [2]).
Letφ:X⟶Y and ψ:Y⟶Z be two wiring diagrams. We define their composition, denoted ψ∘ϕ, as the pair ψ∘ϕin,ψ∘ϕout, where ψ∘ϕin is defined such that the following diagram commutes:(1)and ψ∘ϕout is defined such that the following diagram commutes:(2)Definition 8 (category ofC-boxes and wiring diagrams [2]).
The categoryWC of C-boxes and wiring diagrams is defined as follows:Objects: an object inWC is a C-boxMorphisms: a morphism between twoC-boxes X and Y is a wiring diagram ϕ:X⟶YIdentities: an identity morphism onX is the identity wiring diagramComposition: the composition of wiring diagrams is the composition defined in Definition 7


## 2.4. Monoidal Structure of the Category of Boxes

The categoryWC has a monoidal structure for the parallel composition of boxes that corresponds to the intuitive idea of parallelising boxes.Definition 9 (parallel composition of boxes [2]).
LetX=Xin,Xout and Y=Yin,Yout be two C-boxes.The parallel composition, or sum, ofX and Y, denoted as X⊞Y, is the box X⊞Y=Xin+Yin,Xout+Yout, where + is the sum of C-typed finite sets (cf. Definition 2).The parallel composition of twoC-boxes summarises to the concatenation of both input ports and both output ports.Definition 10 (parallel composition of wiring diagrams [2]).
Letφ:X⟶Y=φin,φout and ψ:Y⟶Z=ψin,ψout be two wiring diagrams.The parallel composition, or sum, ofφ and ψ, denoted as φ⊞ψ, is the wiring diagram φ⊞ψ=φin+ψin,φout+ψout, where + is the sum of C-typed functions (cf. Definition 3).Proposition 3.
The categoryWC has the following properties:(i)
The closed box □, defined as □=0,0, where 0 is the C-typed finite set ∅,∅⟶C defined in Proposition 2.4 is the unit for the sum of boxes ⊞.(ii)
WC has a symmetric monoidal structure for the sum of boxes ⊞, with □ as the unit.Proof.
Refer to [2].


## 2.5. Dependent Product of Boxes

The aim of this section is to extend the notion of dependent product (Definition 4) toC-boxes and wiring diagrams.Definition 11 (dependent product of aC-box [2]).
The dependent productX^ of the C-box X=Xin,Xout is the pair X^=Xin^,Xout^.Remark 1.
The dependent product ofX0⊞X1 is X0⊞X1^=X0in^×X1in^,X0out^×X1out^.Definition 12 (dependent product of wiring diagrams [2]).
The dependent productX^ of the wiring diagram φ:X⟶Y is the pair φ^=φin^,φout^.Remark 2.
The dependent productφ0⊞φ1 is φ0⊞φ1^=φ0in^×φ1in^,φ0out^×φ1out^.Proposition 4.
Letφ:X⟶Y and ψ:Y⟶Z. The dependent product of ψ∘φ is the pair ψ∘φ^=ψ∘φin^,ψ∘φout^, where (i) ψ∘φin^x,z=φin^ψin^z,φout^x,x and (ii) ψ∘φout^x=ψout^φout^x.Proof.
Refer [2].Remark 3.
The dependent product ofC-boxes and wiring diagrams could be described in terms of monoidal functors; however, the codomain of this functor is not C×C as expected, but a category that has the same objects (pairs of objects A,B of C) but whose morphisms are pairs of morphisms fin^,fout^:A0,B0⟶A1,B1 such that fin^ is the morphism fin^:A1×B0⟶A0 in C and fout^ is the morphism fout^:B0⟶B1 in C. The composition law is the one given in Proposition 4.Until now, we have only defined a category ofC-boxes, with interesting properties. These C-boxes are exactly as their name suggests: empty boxes. The extension of the dependent product to C-boxes is a necessary step in order to define the “inhabitants” of C-boxes.


## 3. Discrete Systems and Their Equivalences

In this section and in the rest of this paper, we will consider the special case whereC=Sets. Thus, in general, we will simply call “boxes” what we introduced as “Sets-boxes”. We denote the symmetric monoidal category of boxes as WSets.


### 3.1. Definition and Basic Properties

The notions introduced in this section come from [2]. The properties stated here are proven in the same article.Definition 13 (discrete systems [2]).
LetX=Xin,Xout∈WSets be a box.A discrete system for the boxX, or discrete system for short, is a 4-tuple F=SF,frdt,fupd,sF,0 where(i)
SF∈Sets is the state set of F(ii)
frdt:SF⟶Xout^ is its readout function(iii)
fupd:Xin^×SF⟶SF is its update function(iv)
s0∈SF is its initial stateWe denote byDSX the set of all discrete systems for the box X.Remark 4.
In Proposition 3, we defined the closed box□=0,0, where 0 denotes ∅,τ:∅⟶Sets. Its dependent product is □^=∏p∈∅τp,∏p∈∅τp≅1′,1′, where 1′ is any typed finite set of the form 1,τ:1⟶Sets. As a consequence, we have(3)DS□≅SF,frdt,fupd,sF,0S∈Sets,frdt:S⟶1,fupd:1×SF⟶SF,sF,0∈SF.
In other words, an inhabitant of a closed box is a dynamical system with no inputs and no outputs, just a setS and a function S⟶S.Remark 5.
From a set-theoretic point of view,DSX is too big to be a set. A potential solution is to define the DSX within a set big enough for our purposes; for example, the set Vω1 from the von Neumann hierarchy of sets, which contains the usual sets, vector spaces, measurable spaces, Hausdorff spaces, fields, etc., used in mathematics (Vω×2 suffices [6, Lemma 2.9]).In the following, we will continue to writeDSX (and similarly for mappings) with the state set in SF∈Sets for the sake of understandability, but in case set-theoretic problems emerge, we should not write SF∈Sets but SF∈Vω1.Note that discrete systems can be viewed as a generalisation of automata. They have no final states, and the transition function is always a function, i.e., all discrete systems are deterministic, the input alphabet can be infinite, and the transition function is always defined on every input and every state. Discrete systems are not automata that recognize a language, but rather automata that take any input stream and return an output stream based on the states it transitioned to; that is, discrete systems are a generalisation of transducers as defined in [7]. Alternatively, discrete systems exactly correspond to the sequential automata in [8].We previously viewed general boxes (objects inWSets) as empty frames. Discrete systems are the objects that “live” inside. One can draw a parallel with programming: a C-box is the signature of the function, that is, its accepted types of inputs and outputs, and the discrete system is the actual code of the function.In the rest of the article, we will often represent a discrete systemF=SF,frdt,fupd,sF,0 as the following two-arrow graph:(4)The first function describes how a state and an input are transformed into a new state; the second describes how the state is output, or “read out”. In general, the initial statesF,0∈SF will not be represented in these diagrams though it is implicitly there.Discrete systems are part of the more general class of dynamical systems. We can define other types of dynamical systems depending on the categoryC that we are interested in. If C is the category Euc of Euclidean spaces, then we will refer to continuous systems. For more examples, refer [2].Definition 14 (DS application of a wiring diagram [2]).
Letφ:X⟶Y be a wiring diagram. Let F=SF,frdt,fupd,sF,0∈DSX.The DS application ofφ to F, denoted as DSφF, is the discrete system DSφF=SG,grdt,gupd,sG,0∈DSY such that (i) SG=SF, (ii) grdt:s⟼φout^frdts, (iii) gupd:y,s⟼fupdφin^y,frdts,s, and (iv) sG,0=sF,0.We can viewDSφF as the discrete system, and we obtain from F by implementing the wiring diagram φ.Definition 15 (parallel composition of discrete systems [2]).
LetX0 and X1 be boxes and let Fi=SFi,firdt,fiupd,sFi,0∈DSXii∈2 be discrete systems.
The parallel composition ofF0 and F1, denoted as F0⊠F1, is the discrete system SG,grdt,gupd,sG,0∈DSX0⊞X1 such that (i) SG=SF0×SF1, (ii) sG,0=sF0,0,sF1,0, (iii) grdt=f0rdt×f1rdt:SF0×SF1⟶X0out^×X1out^, and (iv) gupd:X0in^×X1in^×SF0×SF1⟶SF0×SF1 makes the following diagram commute:(5)
We also define the parallel composition ofDSX0 and DSX1, denoted as DSX0⊠DSX1, by(6)DSX0⊠DSX1=F0⊠F1F0∈DSX0,F1∈DSX1.Proposition 5.
Parallel compositionF0,F1⟼F0⊠F1 provides a natural map DSX0×DSX1⟶DSX0⊞X1.Proof.
Refer to [2].Theorem 1.
Definitions 13–15 define a lax monoidal functorDS:WSets⟶Sets.Proof.
Refer to [2].


### 3.2. An External Equivalence Relation on Dynamical Systems

Via the monoidal functorDS, a box contains a specified sort of discrete system (depending on the ports of the box). For an exterior spectator, the content of the box does not matter; what matters is the way it transforms input streams to output streams. Thus, even if two boxes contain different discrete systems, for example, one with an infinite state set, and the other with a finite state set, as long as they both give the same output in response to the same input, then they are viewed as “equivalent” from an external point of view.The following definitions formalise this idea.Definition 16 (input and output streams).
LetF=SF,frdt,fupd,sF,0∈DSX.An input stream (forX) is a finite sequence xin¯=xiini∈n∈Xin^n, where n∈ℕ.The output stream produced by F when givenxin¯, denoted Fxin¯, is the stream xout¯ defined by the following recursive system:(7)s0=sF,0,si+1=fupdxiin,si,xiout=frdtsi+1.We refer to the states that F reaches after having processed the input stream xin¯ as the resulting state of F and denote it Fresxin¯. Formally, if xin¯=xiini∈n, then according to the previous recursive system, the resulting state of F is Fresxin¯=sn.Remark 6.
According to the notation proposed in Section1.1, xin¯=xiini∈n∈Xin^n will be written as xin¯∈Xin^.Remark 7.
Definition 16 is a continuation of the definitions of run maps and behaviours in [8], which are functions that assign, respectively, the resulting state and the last output of the automaton given an input stream. The results we obtain with our notations are similar to those in [8].Definition 17 (equivalence as stream transducers).
LetF=SF,frdt,fupd,sF,0 and G=SG,grdt,gupd,sG,0 be two discrete systems.We say thatF and G are equivalent as stream transducers, and we write F≡G, when ∀xin¯∈Xin^,Fxin¯=Gxin¯.It is easy to see the following.Proposition 6.
The relation≡ is an equivalence relation on the set DSX, for any box X.


### 3.3. An Internal Equivalence Relation on Dynamical Systems

The relation≡ defined above does not give any information on the links between two discrete systems that are equivalent as stream transducers. In this subsection, we define another equivalence relation that provides an internal point of view. We then prove that the two equivalence relations are the same.In the following,X=Xin,Xout is any box.Definition 18 (simulation relation).
Suppose givenF=SF,frdt,fupd,sF,0 and G=SG,grdt,gupd,sG,0 in DSX.We say thatF simulates G, and we write F⊢G, if there exists α:SF⟶SG such that sG,0=αsF,0 and such that α∘fupd=gupd∘idXin^,α and frdt=grdt∘α, that is, preserving the initial state and making the following two diagrams commute:(8)We refer toα as a simulation function: it witnesses the simulation F⊢G.A priori, the simulation relation does not relate the output of the two discrete systemsF and G (though this does follow; see Lemma 2); it only declares a correspondence between both their state sets and update and readout functions. Both discrete systems can work in parallel; their state sets need not be the same, nor even of the same cardinality, but they somehow coordinate via the map α. The function α draws the parallel between the internal machinery of F and that of G.For the rest of the article, we will be more interested in the simulation relationF⊢G than any particular simulation function witnessing it: any one will do.Remark 8.
Definition 18 refers to the existence of morphisms between two automata as described in the automata theory literature [8]. The existence of such morphisms suffices for our purposes. We are a bit more restrictive here, as the outputs need to be the same in both automata, while in the usual definition of morphisms, automata can have different output alphabets, as long as there is a function to convert one output into the other.The simulation relation is not necessarily an equivalence relation and is not enough for our purpose, but we can use it to generate the equivalence relation we actually need.Definition 19 (internal equivalence relation onDSX).
LetF,G∈DSX.We say thatF and G are simulation equivalent, and we write F∼G, if there exists a finite sequence Hii∈N∈DSX such that(9)It is not hard to check the following.Theorem 2.
The equivalence relation∼ is the equivalence relation generated by ⊢; that is, ∼ is the smallest equivalence relation R such that ⊢⊆R.Finally, we need to show that the equivalence relation∼ actually groups discrete systems that have the same behaviour as a stream transducer, in the sense of Definition 17; that is, the external and the internal equivalence relation are the same.Lemma 1.
LetF,G∈DSX. If F≡G, then ∃H∈DSX such that H⊢F and H⊢G.Proof.
LetF=SF,frdt,fupd,sF,0 and G=SG,grdt,gupd,sG,0.TakeH=SH,hrdt,hupd,sH,0 such that (i) SH=s,s′∈SF×SG∃xin¯such  thatFresxin¯=sandGresxin¯=s′, (ii) hupdx,s,s′=fupdx,s,gupdx,s′, (iii) hrdts,s′=frdts, and (iv) sH,0=sF,0,sG,0.Take as simulation functions the respective projectionsπSF and πSG.It is easy to see that the required diagrams in Definition 18 do commute. For alls,s′∈SH, we have hrdt∘πSFs,s′=frdts by defintion of hrdt. Also, for all s,s′∈SH, hrdt∘πSGs,s′=frdts=grdts′ because there exists some stream xin¯ such that F results in s and G results in s′; besides, as F≡G, we have Fxin¯=Gxin¯, which implies frdts=grdts′. Consequently, the diagrams commute and H simulates both F and G.Lemma 2.
LetF,G∈DSX. If F⊢G, then F≡G.Proof.
Follows by induction on the length of an input streamxiini∈n∈Xin^.Theorem 3.
∀
F
,
G
∈
DS
X
,
F
≡
G
⟺
F
∼
G; or equivalently: ≡=∼.Proof.
To prove≡=∼, we need ≡⊆∼ and ∼⊆≡.Suppose first thatF,G∈DSX are dynamical systems such that F≡G. According to Lemma 1, there exists a H∈DSX such that H⊢F and H⊢G, and hence F∼G by Definition 19. This establishes ≡⊆∼.We now show that∼⊆≡. According to Proposition 6, ≡ is an equivalence relation, and according to Lemma 2, ≡ contains ⊢. Theorem 2 states that ∼ is the smallest equivalence relation that contains ⊢; necessarily, we have ∼⊆≡.The goal of this article is to show that the behaviour of a general discrete system can be emulated by some specific wiring of some other discrete system, chosen with constraints (for example, on its internal structure). As far as we know, this result cannot be obtained with a pure equality. However, we have a description of what it means to be equivalent, both from an internal and from an external point of view, with the assurance that, seen as a blackbox, the “inhabited” box remains unchanged.As we are not using real equalities, we need to define relations between sets that correspond to the usual inclusion and equality.Definition 20 (inclusion/equality up to equivalence).
LetA,B⊆DSX. We consider the equivalence relation ∼ from Definition 19 (or, equivalently, in Definition 17).We say thatA is a subset of B up to equivalence, and we write A⊑B, when ∀a∈A,∃b∈B,a∼b.We say thatA is equal to B up to equivalence, or A is equivalent to B, and we write A≈B, when A⊑B and A⊒B.IfF,G:WSets⟶Sets are functors, then we write F⊑G when, for all box X, we have FX⊑GX. We write F≈G, when F⊑G and F⊒G.IfM,N:WSets⟶Sets are mappings (not necessarily functors), then we write M⊆N when, for all boxes X and Y, we have MX⊆NX and MorSetsMX,MY⊆MorSetsNX,NY.


## 3.1. Definition and Basic Properties

The notions introduced in this section come from [2]. The properties stated here are proven in the same article.Definition 13 (discrete systems [2]).
LetX=Xin,Xout∈WSets be a box.A discrete system for the boxX, or discrete system for short, is a 4-tuple F=SF,frdt,fupd,sF,0 where(i)
SF∈Sets is the state set of F(ii)
frdt:SF⟶Xout^ is its readout function(iii)
fupd:Xin^×SF⟶SF is its update function(iv)
s0∈SF is its initial stateWe denote byDSX the set of all discrete systems for the box X.Remark 4.
In Proposition 3, we defined the closed box□=0,0, where 0 denotes ∅,τ:∅⟶Sets. Its dependent product is □^=∏p∈∅τp,∏p∈∅τp≅1′,1′, where 1′ is any typed finite set of the form 1,τ:1⟶Sets. As a consequence, we have(3)DS□≅SF,frdt,fupd,sF,0S∈Sets,frdt:S⟶1,fupd:1×SF⟶SF,sF,0∈SF.
In other words, an inhabitant of a closed box is a dynamical system with no inputs and no outputs, just a setS and a function S⟶S.Remark 5.
From a set-theoretic point of view,DSX is too big to be a set. A potential solution is to define the DSX within a set big enough for our purposes; for example, the set Vω1 from the von Neumann hierarchy of sets, which contains the usual sets, vector spaces, measurable spaces, Hausdorff spaces, fields, etc., used in mathematics (Vω×2 suffices [6, Lemma 2.9]).In the following, we will continue to writeDSX (and similarly for mappings) with the state set in SF∈Sets for the sake of understandability, but in case set-theoretic problems emerge, we should not write SF∈Sets but SF∈Vω1.Note that discrete systems can be viewed as a generalisation of automata. They have no final states, and the transition function is always a function, i.e., all discrete systems are deterministic, the input alphabet can be infinite, and the transition function is always defined on every input and every state. Discrete systems are not automata that recognize a language, but rather automata that take any input stream and return an output stream based on the states it transitioned to; that is, discrete systems are a generalisation of transducers as defined in [7]. Alternatively, discrete systems exactly correspond to the sequential automata in [8].We previously viewed general boxes (objects inWSets) as empty frames. Discrete systems are the objects that “live” inside. One can draw a parallel with programming: a C-box is the signature of the function, that is, its accepted types of inputs and outputs, and the discrete system is the actual code of the function.In the rest of the article, we will often represent a discrete systemF=SF,frdt,fupd,sF,0 as the following two-arrow graph:(4)The first function describes how a state and an input are transformed into a new state; the second describes how the state is output, or “read out”. In general, the initial statesF,0∈SF will not be represented in these diagrams though it is implicitly there.Discrete systems are part of the more general class of dynamical systems. We can define other types of dynamical systems depending on the categoryC that we are interested in. If C is the category Euc of Euclidean spaces, then we will refer to continuous systems. For more examples, refer [2].Definition 14 (DS application of a wiring diagram [2]).
Letφ:X⟶Y be a wiring diagram. Let F=SF,frdt,fupd,sF,0∈DSX.The DS application ofφ to F, denoted as DSφF, is the discrete system DSφF=SG,grdt,gupd,sG,0∈DSY such that (i) SG=SF, (ii) grdt:s⟼φout^frdts, (iii) gupd:y,s⟼fupdφin^y,frdts,s, and (iv) sG,0=sF,0.We can viewDSφF as the discrete system, and we obtain from F by implementing the wiring diagram φ.Definition 15 (parallel composition of discrete systems [2]).
LetX0 and X1 be boxes and let Fi=SFi,firdt,fiupd,sFi,0∈DSXii∈2 be discrete systems.
The parallel composition ofF0 and F1, denoted as F0⊠F1, is the discrete system SG,grdt,gupd,sG,0∈DSX0⊞X1 such that (i) SG=SF0×SF1, (ii) sG,0=sF0,0,sF1,0, (iii) grdt=f0rdt×f1rdt:SF0×SF1⟶X0out^×X1out^, and (iv) gupd:X0in^×X1in^×SF0×SF1⟶SF0×SF1 makes the following diagram commute:(5)
We also define the parallel composition ofDSX0 and DSX1, denoted as DSX0⊠DSX1, by(6)DSX0⊠DSX1=F0⊠F1F0∈DSX0,F1∈DSX1.Proposition 5.
Parallel compositionF0,F1⟼F0⊠F1 provides a natural map DSX0×DSX1⟶DSX0⊞X1.Proof.
Refer to [2].Theorem 1.
Definitions 13–15 define a lax monoidal functorDS:WSets⟶Sets.Proof.
Refer to [2].


## 3.2. An External Equivalence Relation on Dynamical Systems

Via the monoidal functorDS, a box contains a specified sort of discrete system (depending on the ports of the box). For an exterior spectator, the content of the box does not matter; what matters is the way it transforms input streams to output streams. Thus, even if two boxes contain different discrete systems, for example, one with an infinite state set, and the other with a finite state set, as long as they both give the same output in response to the same input, then they are viewed as “equivalent” from an external point of view.The following definitions formalise this idea.Definition 16 (input and output streams).
LetF=SF,frdt,fupd,sF,0∈DSX.An input stream (forX) is a finite sequence xin¯=xiini∈n∈Xin^n, where n∈ℕ.The output stream produced by F when givenxin¯, denoted Fxin¯, is the stream xout¯ defined by the following recursive system:(7)s0=sF,0,si+1=fupdxiin,si,xiout=frdtsi+1.We refer to the states that F reaches after having processed the input stream xin¯ as the resulting state of F and denote it Fresxin¯. Formally, if xin¯=xiini∈n, then according to the previous recursive system, the resulting state of F is Fresxin¯=sn.Remark 6.
According to the notation proposed in Section1.1, xin¯=xiini∈n∈Xin^n will be written as xin¯∈Xin^.Remark 7.
Definition 16 is a continuation of the definitions of run maps and behaviours in [8], which are functions that assign, respectively, the resulting state and the last output of the automaton given an input stream. The results we obtain with our notations are similar to those in [8].Definition 17 (equivalence as stream transducers).
LetF=SF,frdt,fupd,sF,0 and G=SG,grdt,gupd,sG,0 be two discrete systems.We say thatF and G are equivalent as stream transducers, and we write F≡G, when ∀xin¯∈Xin^,Fxin¯=Gxin¯.It is easy to see the following.Proposition 6.
The relation≡ is an equivalence relation on the set DSX, for any box X.


## 3.3. An Internal Equivalence Relation on Dynamical Systems

The relation≡ defined above does not give any information on the links between two discrete systems that are equivalent as stream transducers. In this subsection, we define another equivalence relation that provides an internal point of view. We then prove that the two equivalence relations are the same.In the following,X=Xin,Xout is any box.Definition 18 (simulation relation).
Suppose givenF=SF,frdt,fupd,sF,0 and G=SG,grdt,gupd,sG,0 in DSX.We say thatF simulates G, and we write F⊢G, if there exists α:SF⟶SG such that sG,0=αsF,0 and such that α∘fupd=gupd∘idXin^,α and frdt=grdt∘α, that is, preserving the initial state and making the following two diagrams commute:(8)We refer toα as a simulation function: it witnesses the simulation F⊢G.A priori, the simulation relation does not relate the output of the two discrete systemsF and G (though this does follow; see Lemma 2); it only declares a correspondence between both their state sets and update and readout functions. Both discrete systems can work in parallel; their state sets need not be the same, nor even of the same cardinality, but they somehow coordinate via the map α. The function α draws the parallel between the internal machinery of F and that of G.For the rest of the article, we will be more interested in the simulation relationF⊢G than any particular simulation function witnessing it: any one will do.Remark 8.
Definition 18 refers to the existence of morphisms between two automata as described in the automata theory literature [8]. The existence of such morphisms suffices for our purposes. We are a bit more restrictive here, as the outputs need to be the same in both automata, while in the usual definition of morphisms, automata can have different output alphabets, as long as there is a function to convert one output into the other.The simulation relation is not necessarily an equivalence relation and is not enough for our purpose, but we can use it to generate the equivalence relation we actually need.Definition 19 (internal equivalence relation onDSX).
LetF,G∈DSX.We say thatF and G are simulation equivalent, and we write F∼G, if there exists a finite sequence Hii∈N∈DSX such that(9)It is not hard to check the following.Theorem 2.
The equivalence relation∼ is the equivalence relation generated by ⊢; that is, ∼ is the smallest equivalence relation R such that ⊢⊆R.Finally, we need to show that the equivalence relation∼ actually groups discrete systems that have the same behaviour as a stream transducer, in the sense of Definition 17; that is, the external and the internal equivalence relation are the same.Lemma 1.
LetF,G∈DSX. If F≡G, then ∃H∈DSX such that H⊢F and H⊢G.Proof.
LetF=SF,frdt,fupd,sF,0 and G=SG,grdt,gupd,sG,0.TakeH=SH,hrdt,hupd,sH,0 such that (i) SH=s,s′∈SF×SG∃xin¯such  thatFresxin¯=sandGresxin¯=s′, (ii) hupdx,s,s′=fupdx,s,gupdx,s′, (iii) hrdts,s′=frdts, and (iv) sH,0=sF,0,sG,0.Take as simulation functions the respective projectionsπSF and πSG.It is easy to see that the required diagrams in Definition 18 do commute. For alls,s′∈SH, we have hrdt∘πSFs,s′=frdts by defintion of hrdt. Also, for all s,s′∈SH, hrdt∘πSGs,s′=frdts=grdts′ because there exists some stream xin¯ such that F results in s and G results in s′; besides, as F≡G, we have Fxin¯=Gxin¯, which implies frdts=grdts′. Consequently, the diagrams commute and H simulates both F and G.Lemma 2.
LetF,G∈DSX. If F⊢G, then F≡G.Proof.
Follows by induction on the length of an input streamxiini∈n∈Xin^.Theorem 3.
∀
F
,
G
∈
DS
X
,
F
≡
G
⟺
F
∼
G; or equivalently: ≡=∼.Proof.
To prove≡=∼, we need ≡⊆∼ and ∼⊆≡.Suppose first thatF,G∈DSX are dynamical systems such that F≡G. According to Lemma 1, there exists a H∈DSX such that H⊢F and H⊢G, and hence F∼G by Definition 19. This establishes ≡⊆∼.We now show that∼⊆≡. According to Proposition 6, ≡ is an equivalence relation, and according to Lemma 2, ≡ contains ⊢. Theorem 2 states that ∼ is the smallest equivalence relation that contains ⊢; necessarily, we have ∼⊆≡.The goal of this article is to show that the behaviour of a general discrete system can be emulated by some specific wiring of some other discrete system, chosen with constraints (for example, on its internal structure). As far as we know, this result cannot be obtained with a pure equality. However, we have a description of what it means to be equivalent, both from an internal and from an external point of view, with the assurance that, seen as a blackbox, the “inhabited” box remains unchanged.As we are not using real equalities, we need to define relations between sets that correspond to the usual inclusion and equality.Definition 20 (inclusion/equality up to equivalence).
LetA,B⊆DSX. We consider the equivalence relation ∼ from Definition 19 (or, equivalently, in Definition 17).We say thatA is a subset of B up to equivalence, and we write A⊑B, when ∀a∈A,∃b∈B,a∼b.We say thatA is equal to B up to equivalence, or A is equivalent to B, and we write A≈B, when A⊑B and A⊒B.IfF,G:WSets⟶Sets are functors, then we write F⊑G when, for all box X, we have FX⊑GX. We write F≈G, when F⊑G and F⊒G.IfM,N:WSets⟶Sets are mappings (not necessarily functors), then we write M⊆N when, for all boxes X and Y, we have MX⊆NX and MorSetsMX,MY⊆MorSetsNX,NY.


## 4. Main Results

Before we introduce the actual results of the paper, we need a few more notions.


### 4.1. Algebras and Closures

Definition 21 (algebra).
Given a monoidal categoryC, a functor F:C⟶Sets is called an algebra over C when it is a lax monoidal functor.
In our case,C=WSets and DS is an algebra by Theorem 1.Definition 22 (subalgebra).
LetA:WSets⟶Sets be an algebra over WSets. Let σX,Y:AX×AY⟶AX⊞Y denote its first coherence map (we recall that ⊞ is the parallel composition of boxes (cf. Definition 9)).A functorB:WSets⟶Sets is called a subalgebra of A when (i) X∈WSets,BX⊆AX, and (ii) ∀X,Y∈WSets,∀F∈BX,∀G∈BY,σX,YF,G∈BX⊞Y and ∀φ:X⟶Y∈WSets,∀F∈BX,AφF∈BY.Here,A and B are functors that transform boxes into sets. In our setting, the conditions can be interpreted as follows:(i)
First item: discrete systems generated byB are included in those generated by A(ii)
Second item: the parallel composition of two discrete systemsF and G generated by B is also generated by B.(iii)
Third item:B is stable through wiring diagrams: wiring a discrete system generated by B gives another discrete system generated by B.Note that a subalgebra is itself an algebra.Definition 23 (closure).
LetA:WSets⟶Sets be an algebra over WSets.LetB:ObWSets⟶ObSets be any map such that ∀X∈WSets,BX⊆AX. The closure of B, denoted ClosB, is the intersection of all subalgebras of A that contain BX for all X∈WSets (any intersection of subalgebras is a subalgebra).The closure of a mapB can be understood as the minimal lax monoidal functor (or algebra) containing B.


### 4.2. Memoryless Systems

Our first main result concerns the subclass of discrete systems that we call memoryless. We show that wiring together memoryless systems can lead to systems that have memory.Definition 24 (memoryless discrete systems).
DLetX=Xin,Xout be a box.A memoryless discrete system for the boxX, or memoryless discrete system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSX such that fupd immediately discards the previous state and uses only the current input; formally, fupd factors as(10)fupd=Xin^×SF⟶πXin^Xin^⟶fuSF,for some fu:Xin^⟶SF.We denote byDSMLX the set of all memoryless discrete systems for the box X: DSMLX=SF,frdt,fupd,sF,0∈DSX∃fu:Xin^⟶SF,fupd=fu∘πXin^.We call these discrete systems memoryless because we see the states as a kind of memory. The discrete systems defined above transition from one state to another without checking their current state, i.e., without checking their memory.The following definition is a natural restriction of memoryless discrete systems; as these systems are memoryless, the only goal of their states is to produce the output via their readout function. The simplest case is when the readout function is the identity.Definition 25 (direct-output discrete systems).
LetX=Xin,Xout be a box.A direct-output memoryless discrete system for the boxX, or direct-output discrete system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSX such that (i) SF=Xout^, (ii) frdt=idXout^, and (iii) fupd=fu∘πXin^ for some fu:Xin^⟶Xout^.We denote byDSoutMLX the set of all direct-output discrete systems for the box X:(11)DSoutMLX=SF,frdt,fupd,sF,0∈DSMLXS=Xout^,frdt=idXout^=Xout^,idXout^,fupd,S0∈DSX∃fu:Xin^⟶Xout^,fupd=fu∘πXin^.Remark 9.
The mapsDSML:WSets⟶Sets and DSoutML:WSets⟶Sets are not functors because they are not closed under wiring. Indeed, the whole point is that the result of wiring together memoryless systems is not necessarily memoryless.We can now prove one of the main results of this paper, which is that every discrete system can be obtained (up to equivalence) by a memoryless system and a feedback loop. The feedback loop is responsible for holding the state that was originally in the discrete system.Here is the formal statement.Theorem 4.
Clos
DS
out
ML
≈
DS.Proof.
We haveDSoutML⊆DSML⊆DS, so ClosDSoutML⊆DS; thus, ClosDSoutML⊑DS. We need the opposite inclusion (up to equivalence) ClosDSoutML⊒DS.LetY=Yin,Yout∈WSets and let G=SG,grdt,gupd,sG,0∈DSY. We will find X∈WSets, F∈DSoutMLX and φ:X⟶Y such that DSφF∼G.LetδSG=SG∈TFSSets be the list with one element, SG, and consider the box δSG,δSG with only that port on the left and the right. We define X as the parallel composition of this box δSG,δSG and Y; that is,(12)X=Xin,Xout=δSG,δSG⊞Y=δSG+Yin,δSG+Yout.Note thatXin^=SG×Yin^ and Xout^=SG×Yout^. Thus, if xin¯∈Xin^, then xin¯=s,yin¯. Similarly, if xout¯∈Xout^, then xout¯=s,yout¯.We chooseφ:X⟶Y as the pair φin,φout of coproduct inclusions: (i) φin:δSG+Yin⟶Yin+δSG+Youtx⟼x and (ii) φout:Yout⟶δSG+Youtx⟼x.It follows from definition 12 that their dependent productsφin^:Yin^×SG×Yout^⟶SG×Yin^ and φout^:SG×Yout^⟶Yout^ are projections.Recall that the goal is to findF=SF,frdt,fupd,sF,0∈DSoutMLX such that DSφF∼G. So define F as follows: (i) SF=Xout^=SG×Yout^, (ii) frdt=idXout^, (iii) fupdxin¯,xout¯=fupds,yin¯,s′,yout¯=gupdyin¯,s,grdtgupdyin¯,s, and (iv) sF,0=sG,0,grdtsG,0.It is easy to see thatF is in DSoutMLX because frdt and fupd have the correct form. So let SH,hrdt,hupd,sH,0=DSφF; we need to show it is equivalent to G. We compute each part of DSφF according to Definition 14.Its state set is as follows:(13)SH=SF=Xout^=SG×Yout^.Its readout function is defined on an arbitraryxout as follows:(14)hrdtxout¯=hrdts,yout¯=φout^frdts,yout¯=πYout^idXout^s,yout¯=yout.¯Its update function is defined on an arbitraryyin¯,s,yout¯ as follows:(15)hupdyin¯,s,yout¯=fupdφin^yin¯,frdts,yout¯,s,yout¯=fupds,yin¯,s,yout¯=gupdyin¯,s,grdtgupdyin¯,s.Finally, its start state is as follows:(16)sF,0=sG,0,grdtsG,0Consequently, the following diagram commutes:(17)Here, α=idSG,grdt. This yields G⊢DSφF, and hence, DSφF∼G, which concludes the proof.Corollary 1.
Clos
DS
ML
≈
DS.Corollary 2.
For allG∈DSY, if G has finite state set, then there exists H∈ClosDSMLY with the finite state set such that H∼G.Proof.
In the proof of Theorem 4, takeH=DSφF, but instead of SF=SG×Yout^, take SF=SG×grdtSG⊆SG×Yout^. If SG is finite, so is SF.In that case,H is no more in ClosDSoutMLY but in ClosDSMLY.Corollary 3.
(assuming the axiom of choice) For allG∈DSY, if G has an infinite state set, then there exists H∈ClosDSMLY with a state set of the same cardinality as G, such that H∼G.Proof.
In the proof of Theorem 4, takeH=DSφF, but instead of SF=SG×Yout^, take SF=SG×grdtSG⊆SG×Yout^. The axiom of choice gives cardSF=cardSG×cardgrdtSG=cardSG.In that case,H is no more in ClosDSoutMLY but in ClosDSMLY.Theorem 4 states that systems without memory can be wired together to form systems with memory. In fact, the result is more subtle. It states that, for any discrete system, we can find (or build) a memoryless discrete system with the certain wiring such that both systems are equivalent as stream transducers. The internal equivalence relation described in Theorem 3 is instrumental to prove Theorem 4, while the result is stated with regard to the external equivalence relation.Another interpretation is the following. The mappingDSoutML produces very “degenerate” discrete systems: they do not remember anything, and they do not have real-state spaces; DSoutML really produces nothing more than mathematical functions. The result to see here is that the only thing a discrete system needs to generate memory is really its last output, not necessarily the whole list of inputs and outputs.


### 4.3. Finite-State Systems

The second result is a refinement of Theorem 4 and is somewhat similar to it. We show that wiring together two-state discrete systems can generate a finite-state system with memory.We can view the result as the generalisation of transistors being wired together in order to build a computer, or a system of neurons wired together to form a brain with finite memory.Definition 26 (finite-state systems).
LetX=Xin,Xout be a box.A finite-state discrete system for the boxX, or finite-state system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSX such that SF is a finite set.We denote byDSFinX the set of all finite-state discrete systems for the box X: DSFinX=SF,frdt,fupd,sF,0∈DSXcardSF∈ℕ. For a wiring diagram ϕ, we set DSFinφ=DSφ.It is easy to see the following.Proposition 7.
The mapDSFin:WSets⟶Sets is a subalgebra of DS.Proof.
Follows from Definition 22.Definition 27 (Boolean systems).
LetX=Xin,Xout be a box.
A Boolean memoryless discrete system for the boxX, or Boolean system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSFinX such that F is memoryless and SF=2n=0,1n.
We denote byDSBoolMLX the set of all Boolean memoryless discrete systems for the box X: DSBoolMLX=SF,frdt,fupd,sF,0∈DSMLXSF=0,1n.Remark 10.
The mapDSBoolML:WSets⟶Sets is not a functor, for the same reason as in Remark 9.Lemma 3.
DS
Bool
ML
≈
DS
ML
∩
DS
Fin.Proof.
By construction,DSBoolML⊆DSML∩DSFin, so DSBoolML⊑DSML∩DSFin. We need to show the other inclusion, so let G=SG,grdt,gupd,sG,0∈DSMLX∩DSFinX, and it suffices to show that there is F∈DSBoolMLX with G∼F.We havegupd=gu∘πXin^ and SG finite. Let N=log2cardSG. There exists an injection i:SG⟶2N and a surjection p:2N⟶SG such that p∘i=idSG. This is just a binary encoding of SG.DefineF=SF,frdt,fupd,sF,0 such that (i) SF=2N, (ii) frdt=grdt∘p, and (iii) fupd=gupd∘p and sF,0=isG,0.Then, the following diagram commutes:(18)We haveF∈DSBoolMLX and G⊢F (with i as simulation function), so F∼G, and hence the result.Lemma 4.
DS
Fin
≈
Clos
DS
ML
∩
DS
Fin.Proof.
Observe thatDSFin=DS∩DSFin. By Corollary 1, we have DS≈ClosDSML. In particular, ClosDSML⊆DS, so ClosDSML∩DSFin⊆DS∩DSFin. This gives one inclusion, ClosDSML∩DSFin⊑DS∩DSFin.As for the reverse inclusion (up to equivalence), letX be a box and let F∈DS∩DSFinX. By Corollary 1, there exists G∈ClosDSML such that G∼F. By Corollary 2, we can choose G so that G∈DSFinX and hence the result.Theorem 5.
Clos
DS
Bool
ML
≈
DS
Fin.Proof.
Clearly,ClosDSBoolML⊑DSFin. By Lemma 3, in order to prove DSFin⊑ClosDSBoolML, it suffices to prove DSFin⊑ClosDSML∩DSFin. Furthermore, since DSFin≈ClosDSML∩DSFin (Lemma 4), we reduce to proving that ClosDSML∩DSFin⊑ClosDSML∩DSFin.LetY∈WSets be a box, and let G∈ClosDSML∩DSFinY. We have G∈ClosDSMLY, so according to Corollary 1, there exists a box X∈WSets, a wiring diagram φ:X⟶Y, and a F∈DSMLX such that DSφF∼G. Furthermore, according to Corollary 2, we can choose F with the finite state set. Finally, F∈DSML∩DSFinX, and DSφF∼G, so ClosDSML∩DSFin⊑ClosDSML∩DSFin and hence the result.


## 4.1. Algebras and Closures

Definition 21 (algebra).
Given a monoidal categoryC, a functor F:C⟶Sets is called an algebra over C when it is a lax monoidal functor.
In our case,C=WSets and DS is an algebra by Theorem 1.Definition 22 (subalgebra).
LetA:WSets⟶Sets be an algebra over WSets. Let σX,Y:AX×AY⟶AX⊞Y denote its first coherence map (we recall that ⊞ is the parallel composition of boxes (cf. Definition 9)).A functorB:WSets⟶Sets is called a subalgebra of A when (i) X∈WSets,BX⊆AX, and (ii) ∀X,Y∈WSets,∀F∈BX,∀G∈BY,σX,YF,G∈BX⊞Y and ∀φ:X⟶Y∈WSets,∀F∈BX,AφF∈BY.Here,A and B are functors that transform boxes into sets. In our setting, the conditions can be interpreted as follows:(i)
First item: discrete systems generated byB are included in those generated by A(ii)
Second item: the parallel composition of two discrete systemsF and G generated by B is also generated by B.(iii)
Third item:B is stable through wiring diagrams: wiring a discrete system generated by B gives another discrete system generated by B.Note that a subalgebra is itself an algebra.Definition 23 (closure).
LetA:WSets⟶Sets be an algebra over WSets.LetB:ObWSets⟶ObSets be any map such that ∀X∈WSets,BX⊆AX. The closure of B, denoted ClosB, is the intersection of all subalgebras of A that contain BX for all X∈WSets (any intersection of subalgebras is a subalgebra).The closure of a mapB can be understood as the minimal lax monoidal functor (or algebra) containing B.


## 4.2. Memoryless Systems

Our first main result concerns the subclass of discrete systems that we call memoryless. We show that wiring together memoryless systems can lead to systems that have memory.Definition 24 (memoryless discrete systems).
DLetX=Xin,Xout be a box.A memoryless discrete system for the boxX, or memoryless discrete system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSX such that fupd immediately discards the previous state and uses only the current input; formally, fupd factors as(10)fupd=Xin^×SF⟶πXin^Xin^⟶fuSF,for some fu:Xin^⟶SF.We denote byDSMLX the set of all memoryless discrete systems for the box X: DSMLX=SF,frdt,fupd,sF,0∈DSX∃fu:Xin^⟶SF,fupd=fu∘πXin^.We call these discrete systems memoryless because we see the states as a kind of memory. The discrete systems defined above transition from one state to another without checking their current state, i.e., without checking their memory.The following definition is a natural restriction of memoryless discrete systems; as these systems are memoryless, the only goal of their states is to produce the output via their readout function. The simplest case is when the readout function is the identity.Definition 25 (direct-output discrete systems).
LetX=Xin,Xout be a box.A direct-output memoryless discrete system for the boxX, or direct-output discrete system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSX such that (i) SF=Xout^, (ii) frdt=idXout^, and (iii) fupd=fu∘πXin^ for some fu:Xin^⟶Xout^.We denote byDSoutMLX the set of all direct-output discrete systems for the box X:(11)DSoutMLX=SF,frdt,fupd,sF,0∈DSMLXS=Xout^,frdt=idXout^=Xout^,idXout^,fupd,S0∈DSX∃fu:Xin^⟶Xout^,fupd=fu∘πXin^.Remark 9.
The mapsDSML:WSets⟶Sets and DSoutML:WSets⟶Sets are not functors because they are not closed under wiring. Indeed, the whole point is that the result of wiring together memoryless systems is not necessarily memoryless.We can now prove one of the main results of this paper, which is that every discrete system can be obtained (up to equivalence) by a memoryless system and a feedback loop. The feedback loop is responsible for holding the state that was originally in the discrete system.Here is the formal statement.Theorem 4.
Clos
DS
out
ML
≈
DS.Proof.
We haveDSoutML⊆DSML⊆DS, so ClosDSoutML⊆DS; thus, ClosDSoutML⊑DS. We need the opposite inclusion (up to equivalence) ClosDSoutML⊒DS.LetY=Yin,Yout∈WSets and let G=SG,grdt,gupd,sG,0∈DSY. We will find X∈WSets, F∈DSoutMLX and φ:X⟶Y such that DSφF∼G.LetδSG=SG∈TFSSets be the list with one element, SG, and consider the box δSG,δSG with only that port on the left and the right. We define X as the parallel composition of this box δSG,δSG and Y; that is,(12)X=Xin,Xout=δSG,δSG⊞Y=δSG+Yin,δSG+Yout.Note thatXin^=SG×Yin^ and Xout^=SG×Yout^. Thus, if xin¯∈Xin^, then xin¯=s,yin¯. Similarly, if xout¯∈Xout^, then xout¯=s,yout¯.We chooseφ:X⟶Y as the pair φin,φout of coproduct inclusions: (i) φin:δSG+Yin⟶Yin+δSG+Youtx⟼x and (ii) φout:Yout⟶δSG+Youtx⟼x.It follows from definition 12 that their dependent productsφin^:Yin^×SG×Yout^⟶SG×Yin^ and φout^:SG×Yout^⟶Yout^ are projections.Recall that the goal is to findF=SF,frdt,fupd,sF,0∈DSoutMLX such that DSφF∼G. So define F as follows: (i) SF=Xout^=SG×Yout^, (ii) frdt=idXout^, (iii) fupdxin¯,xout¯=fupds,yin¯,s′,yout¯=gupdyin¯,s,grdtgupdyin¯,s, and (iv) sF,0=sG,0,grdtsG,0.It is easy to see thatF is in DSoutMLX because frdt and fupd have the correct form. So let SH,hrdt,hupd,sH,0=DSφF; we need to show it is equivalent to G. We compute each part of DSφF according to Definition 14.Its state set is as follows:(13)SH=SF=Xout^=SG×Yout^.Its readout function is defined on an arbitraryxout as follows:(14)hrdtxout¯=hrdts,yout¯=φout^frdts,yout¯=πYout^idXout^s,yout¯=yout.¯Its update function is defined on an arbitraryyin¯,s,yout¯ as follows:(15)hupdyin¯,s,yout¯=fupdφin^yin¯,frdts,yout¯,s,yout¯=fupds,yin¯,s,yout¯=gupdyin¯,s,grdtgupdyin¯,s.Finally, its start state is as follows:(16)sF,0=sG,0,grdtsG,0Consequently, the following diagram commutes:(17)Here, α=idSG,grdt. This yields G⊢DSφF, and hence, DSφF∼G, which concludes the proof.Corollary 1.
Clos
DS
ML
≈
DS.Corollary 2.
For allG∈DSY, if G has finite state set, then there exists H∈ClosDSMLY with the finite state set such that H∼G.Proof.
In the proof of Theorem 4, takeH=DSφF, but instead of SF=SG×Yout^, take SF=SG×grdtSG⊆SG×Yout^. If SG is finite, so is SF.In that case,H is no more in ClosDSoutMLY but in ClosDSMLY.Corollary 3.
(assuming the axiom of choice) For allG∈DSY, if G has an infinite state set, then there exists H∈ClosDSMLY with a state set of the same cardinality as G, such that H∼G.Proof.
In the proof of Theorem 4, takeH=DSφF, but instead of SF=SG×Yout^, take SF=SG×grdtSG⊆SG×Yout^. The axiom of choice gives cardSF=cardSG×cardgrdtSG=cardSG.In that case,H is no more in ClosDSoutMLY but in ClosDSMLY.Theorem 4 states that systems without memory can be wired together to form systems with memory. In fact, the result is more subtle. It states that, for any discrete system, we can find (or build) a memoryless discrete system with the certain wiring such that both systems are equivalent as stream transducers. The internal equivalence relation described in Theorem 3 is instrumental to prove Theorem 4, while the result is stated with regard to the external equivalence relation.Another interpretation is the following. The mappingDSoutML produces very “degenerate” discrete systems: they do not remember anything, and they do not have real-state spaces; DSoutML really produces nothing more than mathematical functions. The result to see here is that the only thing a discrete system needs to generate memory is really its last output, not necessarily the whole list of inputs and outputs.


## 4.3. Finite-State Systems

The second result is a refinement of Theorem 4 and is somewhat similar to it. We show that wiring together two-state discrete systems can generate a finite-state system with memory.We can view the result as the generalisation of transistors being wired together in order to build a computer, or a system of neurons wired together to form a brain with finite memory.Definition 26 (finite-state systems).
LetX=Xin,Xout be a box.A finite-state discrete system for the boxX, or finite-state system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSX such that SF is a finite set.We denote byDSFinX the set of all finite-state discrete systems for the box X: DSFinX=SF,frdt,fupd,sF,0∈DSXcardSF∈ℕ. For a wiring diagram ϕ, we set DSFinφ=DSφ.It is easy to see the following.Proposition 7.
The mapDSFin:WSets⟶Sets is a subalgebra of DS.Proof.
Follows from Definition 22.Definition 27 (Boolean systems).
LetX=Xin,Xout be a box.
A Boolean memoryless discrete system for the boxX, or Boolean system for short, is a discrete system F=SF,frdt,fupd,sF,0∈DSFinX such that F is memoryless and SF=2n=0,1n.
We denote byDSBoolMLX the set of all Boolean memoryless discrete systems for the box X: DSBoolMLX=SF,frdt,fupd,sF,0∈DSMLXSF=0,1n.Remark 10.
The mapDSBoolML:WSets⟶Sets is not a functor, for the same reason as in Remark 9.Lemma 3.
DS
Bool
ML
≈
DS
ML
∩
DS
Fin.Proof.
By construction,DSBoolML⊆DSML∩DSFin, so DSBoolML⊑DSML∩DSFin. We need to show the other inclusion, so let G=SG,grdt,gupd,sG,0∈DSMLX∩DSFinX, and it suffices to show that there is F∈DSBoolMLX with G∼F.We havegupd=gu∘πXin^ and SG finite. Let N=log2cardSG. There exists an injection i:SG⟶2N and a surjection p:2N⟶SG such that p∘i=idSG. This is just a binary encoding of SG.DefineF=SF,frdt,fupd,sF,0 such that (i) SF=2N, (ii) frdt=grdt∘p, and (iii) fupd=gupd∘p and sF,0=isG,0.Then, the following diagram commutes:(18)We haveF∈DSBoolMLX and G⊢F (with i as simulation function), so F∼G, and hence the result.Lemma 4.
DS
Fin
≈
Clos
DS
ML
∩
DS
Fin.Proof.
Observe thatDSFin=DS∩DSFin. By Corollary 1, we have DS≈ClosDSML. In particular, ClosDSML⊆DS, so ClosDSML∩DSFin⊆DS∩DSFin. This gives one inclusion, ClosDSML∩DSFin⊑DS∩DSFin.As for the reverse inclusion (up to equivalence), letX be a box and let F∈DS∩DSFinX. By Corollary 1, there exists G∈ClosDSML such that G∼F. By Corollary 2, we can choose G so that G∈DSFinX and hence the result.Theorem 5.
Clos
DS
Bool
ML
≈
DS
Fin.Proof.
Clearly,ClosDSBoolML⊑DSFin. By Lemma 3, in order to prove DSFin⊑ClosDSBoolML, it suffices to prove DSFin⊑ClosDSML∩DSFin. Furthermore, since DSFin≈ClosDSML∩DSFin (Lemma 4), we reduce to proving that ClosDSML∩DSFin⊑ClosDSML∩DSFin.LetY∈WSets be a box, and let G∈ClosDSML∩DSFinY. We have G∈ClosDSMLY, so according to Corollary 1, there exists a box X∈WSets, a wiring diagram φ:X⟶Y, and a F∈DSMLX such that DSφF∼G. Furthermore, according to Corollary 2, we can choose F with the finite state set. Finally, F∈DSML∩DSFinX, and DSφF∼G, so ClosDSML∩DSFin⊑ClosDSML∩DSFin and hence the result.


## 5. Conclusion

Boxes are empty frames that condition the inputs and outputs of their content, a generalisation of automata called discrete systems. Such systems come with a state set that represents their memory of previous inputs. In a sense, discrete systems can learn. However, we can define a subclass of discrete systems that do not store any experience of their past. We see these as reactive, in the sense that they still react to any input, but their past experience does not influence that reaction. Unlike typical discrete systems, they do not keep a memory of the previous inputs.In this paper, we use a category-theoretic framework to give a constructive proof that any discrete system with memory can be simulated by some correctly wired memoryless system. This result can be understood as a phenomenon of emergence in a complex system.This construction opens a number of new questions. A possible question might consist in finding the “best” memoryless system, where “best” could depend on the definition of some valuation function, e.g., the most parsimonious in terms of the state set. A similar question could be asked with respect to wiring diagrams, whose number of feedback loops could be bounded by a cost function.Possible extensions of this work could concern dynamical systems other than DS. We can establish the same kind of results when considering measurable or continuous dynamical systems.



---

*Source: 6803526-2019-10-10.xml*