\chapter{A Deal with Life} \begin{refsection}[bib/sivanov-dblp-mod.bib,bib/sivanov-extra.bib,bib/dealb.bib] Life is one of the most beautiful things in the universe. Arguably, it is because we humans belong to the kingdom of Life that it fascinates us so. Beyond its intrinsic beauty to which our sensory organs are attuned, it also deeply attracts us because of the self-referentiality of its contemplation: when thinking about Life, we often think about our interactions with it, and ultimately about ourselves. Self-referentiality is also a hurdle: it is intrinsically difficult to conceive of oneself. Even though theoretical computer science is no substitute for philosophy, I enjoy taking Gödel's incompleteness theorems\footnote{\url{https://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems}} and especially Hilbert's \emph{Entscheidungsproblem}\footnote{\url{https://en.wikipedia.org/wiki/Entscheidungsproblem}} and the halting problem\footnote{\url{https://en.wikipedia.org/wiki/Halting_problem}} as vivid examples: Turing's famous proof states that a Turing machine cannot generally decide whether another Turing machine will ever halt. Since abstract computing devices can be seen as distant mathematizations of the human brain, this formal result hints that entirely conceiving of our mind---and by extension of Life itself---is borderline intractable. The difficulty of self-referiantiality is also deeply disturbing, especially because understanding how our bodies function within their environments has so many essential implications: dealing with the climate crisis, tackling diseases, improving the quality of life, to only cite the foremost ones. To avoid the worry of looking into the mirror for too long, one can brutally build a wall between oneself and ``the rest'' of Life, and adopt what may be called the Engineer's position: a living organism is a machine constituted out of mechanical pieces, whilst the human disassembles, adjusts, and reassembles them again, improved. Modern biology, medicine, biotechnology illustrate the high performance of the Engineer's approach, and this text is not a criticism of mechanicism per se. Nevertheless, its efficiency does not entail total truthfulness, nor even exclusivity about truth. In other words, mechanistic views allowing for impressive technical achievements does not mean that these views fully reflect reality, nor that mechanicism is the final stop on our journey to understanding Life. In my research, I aim for exploring different approaches to Life and tools supporting such approaches. I take particular enthusiasm in thinking about striking \emph{a deal with Life}: establishing \emph{mutually beneficial} interactions with living systems. Concluding deals as opposed to taking the Engineer's position resets the power balance in our relationship with Life: instead of seeking to control, hack, or otherwise dominate living organisms, the goal is to further take into account their well-being. I believe that approaching Life from this viewpoint is essential if we are after true solutions to fundamental problems such as the climate crisis or complex diseases. On a more philosophical note, the framework of mutually beneficial interactions should remind us that our intelligence in no way warrants an extraction of the human being into an exceptional superior stance---we are part of Life, and we ought to think and act accordingly. \newpage \section{Mechanicism: Where engineering meets biology} \label{sec:mechanicism} In the 20th century, biology was dramatically affected by physics and engineering, and this has brought revolutionary advances in understanding Life and interaction with it~\cite{CornishBowdenCLSA2007,Glade22,Nicholson2019,Woese2004}. Grounding the function of biological structures in the physical reality allowed for convergence of worldview between physics and biology, thereby conferring to the latter the gravitas of a ``real'' science. A remarkable tool physics and engineering brought to biology is reductionism---to understand a system, decompose it into parts, understand each of the parts, and understand the interactions between the parts to get back to the big picture. Reductionism in turn fostered the emergence of mechanicism, the modern proponents of which ``conceive of the cell as an intricate piece of machinery whose organization reflects a pre-existing design, whose structure is wholly intelligible in reductionistic terms, and whose operation is governed by deterministic laws, rendering its behaviour predictable and controllable—at least in principle.''\cite{Nicholson2019} With all due recognition of the major advances yielded by reductionism and mechanicism, it appears hard to believe that this is the final stop on the way to understanding Life. I recall first of all the discussion in~\cite[page~2]{Woese2004} of reductionism as an operational tool allowing to tackle complexity (empirical reductionism), as opposed to the belief that it actually corresponds to the organization of the living matter (fundamental reductionism). Fundamental reductionism makes therefore an additional strong assumption, which impacts the ``sense of what is important'': molecular biology established the molecular level as fundamental, and demoted the status of larger structures---e.g. organisms, ecosystems, etc. These are deemed emergent, and therefore less important, secondary, directly derivable from more fundamental matters. While the notion of emergence in natural sciences is fraught, and its objective qualities can be debated (e.g.~\cite{RonaldSC99}), it has the merit of putting in focus the hierarchy of scales. It is a hierarchy in the sense that, while physics teaches us that the whole is always necessarily the sum of its parts (plus the interactions), it is often irrelevant to put the whole away, and only peer at the components. It is therefore important to not always fall through to the underlying levels, and specifically to avoid Laplace's daemon abuse: the Laplace's daemon\footnote{Laplace's daemon is a thought experiment introducing an imaginary creature which knows exactly the positions and momenta of every atom in the universe. The original conclusion conceived by of Pierre-Simon Laplace in 1814 is that this absolute knowledge should entail full knowledge of past and future positions of these particles~\cite{wikiLaplace}. In modern days, Laplace's daemon is often used as a metaphor for absolute knowledge of the minutae of a complex system, down to its elementary particles.} cannot practically exist, but should it exist, it would in no way have any influence on the fact that we as humans find it extremely useful to operate with concepts situated at higher scales\footnote{An informal inspiration for these observations comes from~\cite{Carroll}.}. It is physics again, and statistical mechanics in particular, that recalls this saliently by deeply relying upon thinking about systems such as gasses in terms of macrostates (volume, pressure, temperature) and microstates (positions and momenta of all particles)~\cite{SusskindCourse,wikiEntropy}. In other words, while one might argue that microstates are more ``fundamental'' in some way, it is of little practical importance, and addressing multiple scales is still pertinent. Fundamental reductionism as a belief is strongly related to engineering, and specifically the practice of constructing complex structures and mechanisms out of simpler building blocks. The multiple ways in which engineering has been durably changing our lives and our surroundings naturally fuels extending its reach beyond human creation, onto living matter. A spectacular manifestation is the Machine Conception of the Cell (MCC) as introduced in~\cite{Nicholson2019}: the cell is seen as an intricate machine, somewhat similar to a computer, which makes it appropriate to use engineering terms to designate the cellular components visible by microscopy: molecular motors, Golgi apparatus, genetic program, pumps, locks, keys, gates, circuitry, etc. The choice of terms is in principle contingent, and it is natural to use words evoking familiar structures, but in practice this reinforces the belief in the truthfulness of the engineering approach. Indeed, scientific papers ubiquitously summarize knowledge in the form of circuits or maps. As stated in~\cite[page~6]{Mayer2009}, ``the typical ‘cartoons’ of signaling pathways, with their reassuring arrows and limited number of states [...] could be the real villain of the piece.'' The Wikipedia page on molecular motors literally starts with the sentence ``Molecular motors are [...] molecular \emph{machines}''\cite{wikiMotors} (the emphasis is mine), and features several animations which would look appropriate in a book on the construction of mechanical toys. The last illustration---and probably the most verbose---of the relationship between reductionism and the Engineer's work I bring here is the very term ``biological engineering''. In fact, widely admitted considerations easily uncover some flaws in the belief in the fundamental nature of the MCC~\cite{Nicholson2019}. To cite two of the most salient ones, the cell is a milieu which is better described as liquid, rather than solid. It is densely packed with various molecules, which do not always strictly respect a certain conformation, but rather continuously evolve across a spectrum of shapes. It being impossible for a human to observe the cellular processes with the naked eye, the researcher is tempted to follow the mindset suggested by the available technology conceived for conceiving of and observing microscopic machines~\cite{Glade22}, a mindset which also happens to be mainstream. Unsurprisingly, if one looks for machines, one finds machines, as the animation ``The Inner Life of the Cell'' conveniently illustrates~\cite{lifeOfTheCell}. Avoiding conceptual frameworks other than fundamental reductionism and mechanicism not only forces our thinking into a certain box which partially corresponds to reality, but also biases our methodology of interactions with Life. When one imagines the cell as a machine, one expects mechanistic explanations, building upon strong causality. When the computer screen shows a picture or a car modifies its trajectory, it is always possible to indicate a satisfactory set of causes. This is because the engineers who built the device had a specific intention in mind, which can be relatively easily unpacked. Biological systems originated from spontaneous evolution, without anyone human baking in specific goals, implying that causality is much harder to establish convincingly. Yet, reductionism and mechanicism tempt the researches to only look for correlations which may be interpreted as causal: ``It is much easier to write and publish a paper suggesting Protein X is necessary for transmitting a signal from A to B, than one showing that Protein X is one of many potential components of a heterogeneous ensemble of signaling complexes that together couple A to B.''~\cite{Mayer2009}. While the Machine Conception of the Cell and similar mechanistic points of view are not oblivious to the intrinsic noise of the respective biological systems, seeing them as machines invites to treating noise as a nuisance which the biological systems manage to successfully combat in every moment of their existence. However, multiple indications exist that noise plays an essential role, as a matter of fact making some processes possible. We cite as an example the Brownian ratchet model of intracellular transport, which has been gaining considerable traction recently~\cite{Nicholson2019}, and which essentially consists in hypothesising that molecular motors feature two distinct conformations of the energy landscape---a flat one and a saw-toothed one. By periodically switching between the two, the motor buffeted by thermal fluctuations will tend to advance along the cytoskeletal track it is attached to (Figure~\ref{fig:ratchet-motor}). \begin{figure} \centering \tikzstyle axis=[->] \tikzstyle movement=[-{Latex[width=1.2mm]},semithick] \tikzstyle landscape=[very thick,cap=round] \tikzstyle motor=[draw,circle,thick,minimum size=3.5mm] \tikzstyle motorFlip=[motor] \tikzstyle motorFlop=[motor,fill=black!40] \tikzstyle motorGhost=[motor,densely dotted] \newcommand{\landscapeXOff}{.2mm} \newcommand{\landscapeYOff}{1mm} \newcommand{\xLength}{56mm} \newcommand{\yLength}{11mm} \newcommand{\graphSkip}{\vspace{-3mm}} \newcommand{\stepLabOff}{-7mm} \begin{tikzpicture} \draw[axis] (0,0) -- node[midway,xshift=\stepLabOff,minimum width=7mm] {\small (1)} (0,\yLength) node[xshift=3mm] {$U$}; \draw[axis] (0,0) -- (\xLength, 0) node[yshift=-2mm,xshift=-1mm] {$x$}; \draw[landscape] (\landscapeXOff,\landscapeYOff) -- +(52mm,0); \node[motorFlip] (motor) at (11mm,3mm) {}; \node[motorGhost] at ($(motor)-(3.5mm,0)$) {}; \node[motorGhost] at ($(motor)-(6mm,0)$) {}; \node[motorGhost] at ($(motor)+(3.5mm,0)$) {}; \node[motorGhost] at ($(motor)+(6mm,0)$) {}; \coordinate[above=2mm of motor] (arrowAnchor); \draw[movement] ($(arrowAnchor)-(2mm,0)$) -- +(-6mm,0); \draw[movement] ($(arrowAnchor)+(2mm,0)$) -- +(6mm,0); \end{tikzpicture} \graphSkip \begin{tikzpicture} \draw[axis] (0,0) -- node[midway,xshift=\stepLabOff,minimum width=7mm] {\small (2)} (0,\yLength) node[xshift=3mm] {$U$}; \draw[axis] (0,0) -- (\xLength, 0) node[yshift=-2mm,xshift=-1mm] {$x$}; \draw[landscape] (\landscapeXOff,\landscapeYOff) -- ++(2mm,5mm) -- ++(11mm,-5mm) -- ++(2mm,5mm) -- ++(11mm,-5mm) -- ++(2mm,5mm) -- ++(11mm,-5mm) -- ++(2mm,5mm) -- ++(11mm,-5mm); \node[motorFlop] (motor) at (25.2mm,3.7mm) {}; \coordinate[above=2mm of motor] (arrowAnchor); \draw[movement] ($(arrowAnchor)-(2mm,0)$) -- +(-4.5mm,0); \draw[movement] ($(arrowAnchor)+(2mm,0)$) -- +(9mm,0); \end{tikzpicture} \graphSkip \begin{tikzpicture} \draw[axis] (0,0) -- node[midway,xshift=\stepLabOff,minimum width=7mm] {\small (3)} (0,\yLength) node[xshift=3mm] {$U$}; \draw[axis] (0,0) -- (\xLength, 0) node[yshift=-2mm,xshift=-1mm] {$x$}; \draw[landscape] (\landscapeXOff,\landscapeYOff) -- +(52mm,0); \node[motorFlip] (motor) at (25.2mm,3mm) {}; \node[motorGhost] at ($(motor)-(3.5mm,0)$) {}; \node[motorGhost] at ($(motor)-(6mm,0)$) {}; \node[motorGhost] at ($(motor)+(3.5mm,0)$) {}; \node[motorGhost] at ($(motor)+(6mm,0)$) {}; \coordinate[above=2mm of motor] (arrowAnchor); \draw[movement] ($(arrowAnchor)-(2mm,0)$) -- +(-6mm,0); \draw[movement] ($(arrowAnchor)+(2mm,0)$) -- +(6mm,0); \end{tikzpicture} \graphSkip \begin{tikzpicture} \draw[axis] (0,0) -- node[midway,xshift=\stepLabOff,minimum width=7mm] {\small (4)} (0,\yLength) node[xshift=3mm] {$U$}; \draw[axis] (0,0) -- (\xLength, 0) node[yshift=-2mm,xshift=-1mm] {$x$}; \draw[landscape] (\landscapeXOff,\landscapeYOff) -- ++(2mm,5mm) -- ++(11mm,-5mm) -- ++(2mm,5mm) -- ++(11mm,-5mm) -- ++(2mm,5mm) -- ++(11mm,-5mm) -- ++(2mm,5mm) -- ++(11mm,-5mm); \node[motorFlop] (motor) at (38.2mm,3.7mm) {}; \coordinate[above=2mm of motor] (arrowAnchor); \draw[movement] ($(arrowAnchor)-(2mm,0)$) -- +(-4.5mm,0); \draw[movement] ($(arrowAnchor)+(2mm,0)$) -- +(9mm,0); \end{tikzpicture} \caption{A schematic illustration of the Brownian ratchet model of molecular motors. A motor is shown as a circle (\protect\tikz[baseline,yshift=1.2mm]\protect\node[motorFlip,minimum size=2.5mm]{}; or \protect\tikz[baseline,yshift=1.2mm]\protect\node[motorFlop,minimum size=2.5mm]{};), and its energy landscape is shown as a thick line \protect\tikz[baseline,yshift=.2em]\protect\draw[landscape] (0,0) -- (2ex,0);. The horizontal axis $x$ represents the motor's position on the cytoskeletal track, while the vertical axis $U$ illustrates the motor's free energy. The motor is hypothesized to feature two distinct potential energy landscapes, depending on its conformational state. In the flip conformation \protect\tikz[baseline,yshift=1.2mm]\protect\node[motorFlip,minimum size=2.5mm]{};, the energy landscape is flat so the protein may slide freely in one of the two directions, with equal probability for both directions. In the flop conformation \protect\tikz[baseline,yshift=1.2mm]\protect\node[motorFlop,minimum size=2.5mm]{};, the saw-tooth shape of the landscape favors the motor moving to the right, illustrated by a longer arrow pointing to the right. When cycles of ATP hydrolysis make the motor periodically switch between the two conformations, thermal fluctuations will tend to push it to the right. (The original figure is~\cite[Figure~4]{Nicholson2019}, itself a reproduction from~\cite{Kurakin2006}.)} \label{fig:ratchet-motor} \end{figure} \section{The Deal: Mutually beneficial interactions} \label{sec:deals} Seeing Life as an ensemble of machines biases how we expect to collect profit from acting on it. Machine means control: we are constantly looking for knobs which we could turn this or that way, and which could modify the behavior of the system to fit our needs and expectations. This can be seen both at the very practical level, where bioengineers seek to modify bacteria to produce chemicals, e.g.~\cite{berkleyBio}, and also at the theoretical level, where researchers develop methodologies to support looking for the coveted knobs, e.g.~\cite{PardoID21,Vogel2008,Zanudo2015}. If we admit that the reductionistic and mechanistic approach is not globally true, we must accept that these knobs may not necessarily have a definitive shape, but rather be a complex assemblage of factors, affecting the trajectory of the system in multiple non-trivial ways, and possibly shifting in time. Finally, this control mindset introduces an asymmetric relationship between the controller and the controlled, which is unnatural biological context because both the controller and the controlled are made out of the same kind of matter, and are ultimately embedded in the same environment. This chapter outlines a conceptual framework putting symmetry back into the picture, \emph{the Deal with Life}: instead of surreptitiously lifting the human above and out of the living matter by self-designating ourselves as superior Engineers, I propose to account for the fact that we act \emph{within} Life and its complex feedback loops by looking to organize \emph{mutually beneficial interactions} with the living systems, as opposed to trying to control, hack, or engineer them. Since we are talking about the general mindset, the choice of words in not contingent: controlling, hacking, and engineering impose a vertical power relationship, while thinking in terms of mutual benefit admits that our target system has a trajectory of its own, which we would like to preserve it to some degree. Playing with words and summarizing the control-hack-engineer mindset as ``We control, Life obeys'' makes the power imbalance even more striking. Today, the most obvious inspiration for considering mutual benefit comes from the climate crisis: for centuries, we have acted on the environment expecting it to behave like a heat bath, i.e., to absorb whatever we throw at it without essentially changing its state. Besides brandishing a certain naïveté, this point of view is so difficult to abandon that is has become the epitome of science denial according to certain studies, e.g.~\cite{BjornbergKGH2017,ONeillB2010,wikiClimate}, as well as~\cite[page~155]{DryzekNS2011}. As these references and multiple others show, refusing to admit human cause as central to the climate crisis has been invariably and strongly supported by the fossil fuel industry. I suspect nevertheless that one of the reasons for the resilience of the denialist mindset is the deeply anchored feeling that we are engineers and the environment a mere tool. My own inspiration for the Deal with Life comes from theoretical biology discussions with Nicolas \textsc{Glade} at the TIMC lab in Grenoble\footnote{\url{https://www.timc.fr/}}, and specifically from the remarks outlined in Section~\ref{sec:mechanicism} above concerning the dominance of the engineering mindset in modern biology, especially in molecular biology, and the ruts it forces our thinking in. Thinking about mutual benefit in dealing with Life unpacks multiple different levels of caring about the destiny of the system of interest: \begin{itemize} \item \emph{Level 0}: This is the Engineer's mindset: fundamental reductionism and mechanicism---we control, Life obeys. At this level, we do not conceive of any kind of benefit to the target system. \item \emph{Level 1}: We aim to preserve the destiny of the target system to a certain degree. If it is a yeast population, we may want to not allow its size below a certain threshold, or if it is a farm animal, we may want to ensure a certain quality of life according to a set of measures. \item \emph{Level 2}: We aim to benefit the target system to a certain degree, while also extracting our own profit from the interaction. In the case of a farm animal, we may want to ensure that its the state of well-being be \emph{improved} in the context of its interaction with respect to a life without any human intervention. \end{itemize} All three levels of this hierarchy of mutual benefit are in fact already present in our interactions with living organisms. Respecting Level 1 is almost ubiquitously needed, since otherwise we may kill the system of interest before it is capable of producing the deliverable we are after. Level~2 manifests itself to different degrees in interactions with domesticated animals, especially in the context of increased awareness of the conditions to which livestock are typically treated in modern agriculture. Levels 1 and 2 are also progressively making their way to prominence in dealing with ecosystems: cutting down forests brings about various kinds of catastrophes, so it is now laudable to curb deforestation, and even to conduct reforestation campaigns. It would seem on the other hand that biomedical research is stubbornly fond of ignoring Levels~1 and 2, and instead focuses on proudly brandishing the Engineer's Level 0, claiming that if something does not work out today, it will certainly work out tomorrow, provided that tomorrow brings around more energy, more computing power, more workforce, more data. Yet again, in no way do I aim to deny or minimize the benefits of mechanicism and reductionism in biology---which has been instrumental in multiple groundbreaking achievements over the 20th century and beyond. I insist nevertheless that exclusively sticking to Level 0 of the hierarchy of mutual benefit is a fundamental limitation of thought. Lifting this limitation will undoubtedly open up a multitude of new approaches and solutions, as this chapter attempts to outline. A final argument for taking into consideration the destiny of the system of interest which has been lurking around the corner the whole time is that we as humans do not often have a choice on this matter: the living system serving as a target is often required to survive our intervention, and sometimes to maintain the majority of the functions it had before the intervention. That biomedical research is reluctant to go from accepting this obvious constraint to taking more holistic approaches including mutual benefit is possibly due to the complexity that awaits us on the very threshold of the comfortable Engineer's mindset. In other words, it is much easier to see the disease as separate from the carrying organism, and imagine curative strategies tightly focused on a well defined set of diseased structures than to admit that the onset of the disease is a consequence of a complex interplay of multiple factors. Indeed, conceiving of diseases from this more holistic viewpoint is often prohibitively complex with the currently available data and knowledge, all while the reductionist approach gives at least some solutions. I claim however that this is no way should hinder our motivation to tackle the complexity of the more holistic approach. Finally, the way I employ the terms ``deal'' and ``mutual benefit'' corroborates no particular social ideology. The Deal with Life simply calls for including the potential benefit of the target system into the picture by establishing a measure of it. It is up to the protagonists of the concrete context, problem, or practical application to decide whether, how much, and in which way to prioritize this benefit over the profit we humans are expecting to extract. \section{The Deal: A conceptual maquette} \label{sec:maquette} This section aims to provide an overview of the Deal with Life framework for thinking about mutually beneficial interactions with living systems, without focusing on the formal details. Properly formalizing the ideas exposed in this section is a significant part of my future research. A formalization of the Deal with Life is structured into two stages: \begin{enumerate} \item abstract general framework, \item concrete implementations. \end{enumerate} The abstract general framework rigorously defines the main concepts: the interacting systems, their benefits, etc., while concrete implementations instantiate these definitions for concrete systems, supplying additional concepts and tools applicable to the concrete case. Concrete implementations in their own turn occur on two levels: concrete formal dynamical systems---e.g., membrane systems, Boolean networks, string rewriting systems\footnote{The subsequent chapters of this manuscript describe these formal dynamical systems in more detail.}---and concrete biological systems---e.g., a human, population of yeasts, a plant, an ecosystem, etc. Note that while the introductory discourse heavily focuses on how we as humans interact with Life, the Deal with Life framework can be adapted to characterizing and evaluating the interactions between other living systems, not necessarily involving the human. \subsection{Dynamical systems} \label{sec:ds} Following the spirit of~\cite{Thom1974,Zeeman1976}, I propose to use the language of abstract dynamical systems for the general framework of the Deal. In this subsection I quickly recall the main notions, and I refer to sources like~\cite{Brown2018,wikiDS} for more general and more detailed definitions. An \emph{abstract dynamical system} over the state space $X$ and time $T$ is a (partial) function $\Phi : X \times T \to X$ assigning to a state $s \in X$ the new state $\Phi(s, t)$ in which the system will be after time $t \in T$. The function $\Phi$ satisfies the following two natural properties: \begin{enumerate} \item $\Phi(s, 0) = s$: the system does not change its state in 0 time, \item $\Phi(\Phi(s, t_1), t_2) = \Phi(s, t_1 + t_2)$: evolving the system for time $t_1$, then for time $t_2$ leads to the same state as evolving the systems for time $t_1 + t_2$. \end{enumerate} A common shape for a state is an $n$-vector of real parameters of a system---in which case $X \subseteq \mathbb{R}^n$---but no particular restrictions are imposed: $X$ may be a more a general algebraic object. In the most general setting, $T$ is a monoid, but it is rather customary for the time domain to be a contiguous infinite subset of either $\mathbb{Z}$ or $\mathbb{R}$. In the first case, $\Phi$ is usually called a discrete-time dynamical system, and in the second case $\Phi$ is called a continuous-time dynamical system. If additionally the state space $X$ of a discrete-time dynamical system $\Phi : X \times T \to T$ with $T \subseteq \mathbb{Z}$ is discrete (countable), then $\Phi$ is called a discrete dynamical system. Finally, if $X$ is a finite set, then $\Phi$ is called a finite dynamical system. In the case of discrete-time dynamical systems, the time variable can be interpreted as the number of evolution steps. More concretely, for a $t > 0$, $\Phi(s, t)$ can be seen as the state of the system after $t$ steps, while $\Phi(s, -t)$ can be seen as the state the system \emph{was in} $t$ steps ago. When $T = \mathbb{N}$, it is customary to see the discrete-time dynamical systems as the function $F : X \to X$, giving the state to which the dynamical system transitions from state $s \in X$: $F(s) = \Phi(s, 1)$ (e.g,~\cite[Chapter~1]{Riva22}). $F$~generates the possibly infinite state graph of the discrete-time dynamical system, whose nodes are the states, and there is a directed edge from state $s_1$ to state $s_2$ if $s_2 = F(s_1)$. Given a dynamical system $\Phi : X \times T \to X$ and a state $s \in X$, it is possible to construct the restricted function $\Phi_s : T \to X$, $\Phi_s(t) = \Phi(s, t)$, determining the \emph{trajectory} of $\Phi$ through $s$. $\Ima \Phi_s = \{\Phi(s, t) \mid t\in T\}$. If $T = \mathbb{Z}$ or $T = \mathbb{R}$, then the trajectory $\Ima \Phi_s$ can be interpreted as the set of all states through which $\Phi$ goes before and after reaching $s$. If $T = \mathbb{N}$, then the trajectory through $s$ is the iteration of $F$: $\{F^k(s) \mid k \in \mathbb{N}\}$, where $F^0(s) = s$, $F^1(s) = F(s)$, $F^2(s) = F(F(s))$, etc. While I will give most of the general definitions for abstract dynamical systems, I will rely on discrete-time dynamical systems with $T = \mathbb{N}$ later on in the manuscript, for the following reasons: \begin{enumerate} \item discrete time yields simpler formal systems, which can capture a wider range of features before becoming too complex to comprehend, \item discrete time is sufficient to represent the majority of time-related concepts, e.g., event ordering, situating measurements in time, etc. \end{enumerate} Last but not least, this choice is motivated by my own expertise as a computer scientist lying in the field of discrete dynamical systems. \subsection{Determinism, reversibility, stochasticity} \label{sec:det-rever-stoch} The type of the function $\Phi$ as shown in the previous section imposes \emph{deterministic} behavior: for any time interval $t\in T$, $\Phi : X \times T \to X$ assigns to every state $s \in X$ exactly one state $\Phi(s, t)$. Furthermore, when $T = \mathbb{Z}$ or $T = \mathbb{R}$, the system is \emph{reversible}: to any state $s$ and any time interval $t > 0$, $\Phi$ associates exactly one state $\Phi(s, -t)$. In the case $T = \mathbb{Z}$, this implies that every state $s \in X$ has exactly one preimage under the function $F$: $|F^{-1}(s)| = 1$. While it is true that any non-deterministic Turing machine $\mathcal{N}$ can be simulated by a deterministic Turing machine which explores all non-deterministic branches of the computations of $\mathcal{N}$, and Bennett showed in~\cite{Bennett1973} how any Turing machine can be made reversible, determinism and reversibility are quite strong restrictions. In particular, for discrete-time dynamical systems, the state graph generated by $F$ is a set of chains~\cite{DotyKLOSW2023}, i.e., it can be represented in the plane as a set of linear parallel non-intersecting oriented paths. Despite the fact that non-determinism and reversibility do not increase the computational power of Turing machines, these restrictions may have a significant impact in weaker models of computation. On the other hand, non-determinism and irreversibility are useful ingredients to have for practical reasons when building models of reality: indeed, our intuitive perception is that many phenomena in the world around us are non-deterministic, and most of them appear irreversible\footnote{Here, I will only point the reader to~\cite{CarrollArrowFAQ2007} for an entry point into the fascinating discussion of the irreversibility observed in the macroscopic world as opposed to the reversibility of the microscopic world.}. A general way to capture the fact that a phenomenon may go different ways at some point are stochastic processes, which can be defined as sequences of random variables, each of which describes the possible outcomes at a given moment of time~\cite{wikiStochastic}. In general, stochastic processes can also describe irreversible processes, e.g., because the total number of possible outcomes may decrease over time. In the case of discrete-time dynamical systems with $T = \mathbb{N}$, non-determinism can be represented in an arguably simpler way by modifying the type of $F$ to be $F : X \to 2^X$, meaning that for a state $s$, $F(s) \subseteq X$ represents the set of possible next states. The notion of the state graph can be naturally extended by defining it as graph whose set of nodes is $X$ and which contains an edge from $s_1 \in X$ to $s_2 \in X$ if $s_2 \in F(s_1)$. Modifying the type of $F$ in this way enriches the state graph in two ways: \begin{enumerate} \item a state $s \in X$ may have no successor states, i.e., $F(s) = \emptyset$, \item they may be multiple edges originating at the same state $s \in X$ if $|F(s)| > 1$. \end{enumerate} It is further possible to enrich the structure of $F$ by annotating the next states in $F(s)$ with probabilities. More concretely, the type of $F$ can be further extended to $F : X \to 2^{X \times \mathbb{R}}$, thus making $F$ produce sets of pairs (state, probability), with the normalization condition that for every $s$ for which $F(s) \neq \emptyset$ the probabilities of the next states amount to 1: $\sum_{(s', p) \in F(s)} p = 1$. In the rest of the manuscript I use the following terminology for designating different types of discrete-time dynamical systems with $T = \mathbb{N}$, depending on the type of $F$: \begin{itemize} \item $F : X \to X$: \emph{deterministic} discrete-time dynamical system, or deterministic DDS; \item $F : X \to 2^X$: \emph{non-deterministic} discrete-time dynamical system, or non-deterministic DDS; \item $F : X \to 2^{X \times \mathbb{R}}$ with the normalization condition from the previous paragraph: \emph{stochastic} discrete-time dynamical system, or stochastic DDS. \end{itemize} Note how understanding discrete-time dynamical systems as a function assigning states to states (i.e., of one of the types above) allows separating non-determinism from stochasticity. Indeed, according to the preceding discussion, non-determinism describes the possibility of a state to have more than one successor state, while stochasticity means that, in addition, a probability distribution is defined on the set of successor states. Transposing this separation between non-determinism and stochasticity to general dynamical systems defined as $\Phi : X \times T \to X$ seems at least syntactically cumbersome, and the traditional way of capturing non-determinism via stochastic processes as sequences of random variables includes probability distributions from the start. The definition of a trajectory in the case of non-deterministic and irreversible dynamical systems depends on the choice of formalism, but any definition should respect the intuition that a trajectory is a set of states the dynamical system may traverse. In the case of non-deterministic DDS defined as above, a trajectory is a sequence of states $(s_i)_{i \in T}$ such that $s_{i+1} \in F(s_i)$. Similarly, in the case of stochastic DDS, a trajectory is a sequence of state $(s_i)_{i \in T}$ such that there exists a probability $p$ yielding the pair $(s_{i+1}, p) \in F(s_i)$. \printbibliography[heading=subbibliography] \end{refsection} %%% Local Variables: %%% TeX-engine: luatex %%% TeX-master: "hdr" %%% reftex-default-bibliography: ("bib/dealb.bib" "bib/sivanov-dblp-mod.bib" "bib/sivanov-extra.bib") %%% End: