<div dir="auto">Jon,<div dir="auto">Thanks for the clarifications on your current focus.</div><div dir="auto"><br></div><div dir="auto">Problems where the process is at least as important as the result vary greatly, so multiple types of implementation might apply.</div><div dir="auto"><br></div><div dir="auto">I think of Eugenio Moggi's monads as a way to cheat in functional programming by encapsulating extra state. Same with monads in category theory augmenting functors with data type. Same with posets as a way of associating structure onto undifferentiated sets. Same with closures in Lisp to bind the environment with a supposedly pure lambda function in order to have different behaviors.</div><div dir="auto"><br></div><div dir="auto">Memorizing and other forms of caching also bind external data, here with the specific goal of skipping repeated calculations or data transfers.</div><div dir="auto"><br></div><div dir="auto">I have used Petri nets to optimize multiple resources in a system of elevators and to assign the parallel use of components of a CDC 1604 computer. PROLOG is often applied to conundrum type problems. Same with Bayesian networks. In all these cases, precisely known logic rules drive the search for an optimal solution. </div><div dir="auto"><br></div><div dir="auto">Another approach in algorithmically intractable situations especially where the constraints are probability distributions is to search for hidden parameters given external structure with Markov Chain Monte Carlo simulation. Reinforcement learning is another example of searching a large process space.</div><div dir="auto"><br></div><div dir="auto">I lean toward distributed computations like swarms of evolving agents as a way of incorporating state and path dependence. I like the way random connections in reservoir computing mechanisms like liquid state machines and echo state networks can navigate chaotic processes and can be quickly retrained for different constraints.</div><div dir="auto"><br></div><div dir="auto">Finite element analysis could be adapted to solve diffusion limited aggregation or related problems. The "grid" would adapt during the simulation to work at the frontier of the bound and free states. This could apply more generally to Ising models and cellular automata where the computational focus is local and usually sparse.</div><div dir="auto"><br></div><div dir="auto">I say finite element "grid" because that has been the traditional way to cover large computational surfaces as in vector computing or GPUs or Tensor Processing Units, but more appropriate structures for local activity would be ragged arrays or other types of sparse structures implementing quasi-crystaline patterns or random graphs.</div><div dir="auto"><br></div><div dir="auto">Quantum simulation of molecular networks seems like the ultimate way to distribute computation and state with infinite numbers of paths.</div><div dir="auto"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Sep 8, 2020, 8:57 PM Jon Zingale <<a href="mailto:jonzingale@gmail.com">jonzingale@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_default" style="font-size:small;color:rgb(51,51,51)"><font face="verdana, sans-serif">RogerF,</font><br><br><font face="verdana, sans-serif">What I am calling </font><i style="font-family:verdana,sans-serif">maximally-stateful</i><font face="verdana, sans-serif"> is a limiting notion opposed to</font><br><font face="verdana, sans-serif">that of </font><i style="font-family:verdana,sans-serif">purely functional</i><font face="verdana, sans-serif">. Effectively, a </font><i style="font-family:verdana,sans-serif">maximally stateful</i><font face="verdana, sans-serif"> process</font><br><font face="verdana, sans-serif">is one whose side-effects dominate the computation, with little else</font><br><font face="verdana, sans-serif">analytically calculable. At present, I am thinking of things like clouds,</font><br><font face="verdana, sans-serif">cellular automata, or the geological history of a mountain. I am thinking</font><br><font face="verdana, sans-serif">about computations where: the term </font><i style="font-family:verdana,sans-serif">process</i><font face="verdana, sans-serif"> is more apt than </font><i style="font-family:verdana,sans-serif">function</i><font face="verdana, sans-serif">,</font><br><font face="verdana, sans-serif">computations whose specification may be trivial and yet depend crucially</font><br><font face="verdana, sans-serif">on their initial conditions, the evolving </font><i style="font-family:verdana,sans-serif">process</i><font face="verdana, sans-serif"> manifests in bouts of</font><br><font face="verdana, sans-serif">combinatorial explosions, the </font><i style="font-family:verdana,sans-serif">intension</i><font face="verdana, sans-serif"> matters more than the </font><i style="font-family:verdana,sans-serif">extension</i><font face="verdana, sans-serif">,</font><br><font face="verdana, sans-serif">and any particular run is unambiguously path-dependent.</font><br><br><font face="verdana, sans-serif">Some time ago, on the list, Glen mentioned diffusion-limited aggregation</font><br><font face="verdana, sans-serif">(DLA) in the context of our on-going discussions centered around modal</font><br><font face="verdana, sans-serif">logic, determinism, and epiphenomena. Glen suggested DLAs as an example</font><br><font face="verdana, sans-serif">of where the conceptual cleanliness of algebraic thinking, categorical</font><br><font face="verdana, sans-serif">thought, and </font><i style="font-family:verdana,sans-serif">purely functional</i><font face="verdana, sans-serif"> programming may be disadvantageous to the</font><br><font face="verdana, sans-serif">reasoner. Part of his criticism focuses on insufficient characterization</font><br><font face="verdana, sans-serif">by way of Poset-centric descriptions. Inspired by Glen's skepticism, I</font><br><font face="verdana, sans-serif">set out to explore what forms </font><i style="font-family:verdana,sans-serif">purely functional</i><font face="verdana, sans-serif"> diffusion-limited</font><br><font face="verdana, sans-serif">aggregation may take. To a first approximation, the computation may</font><br><font face="verdana, sans-serif">be understood as a function taking a pair of lists to a pair of lists,</font><br><br><font face="monospace">DLA1 :: ([Free], [Bound]) -> ([Free], [Bound])</font><font face="verdana, sans-serif">,</font><br><font face="verdana, sans-serif">where Free and Bound are </font>type<font face="verdana, sans-serif"> synonymous with a general particle type.</font><br><br><font face="verdana, sans-serif">Initially, the collection [Bound] consists of stationary germs and the</font><br><font face="verdana, sans-serif">collection [Free] consists of random walking particles. As freely moving</font><br><font face="verdana, sans-serif">particles enter the neighborhoods of bound particles, the free particles</font><br><font face="verdana, sans-serif">themselves become bound. Functionally, we can interpret the function as a</font><br><font face="verdana, sans-serif">process taking elements from the left list to elements of the right list.</font><br><font face="verdana, sans-serif">However, if this were all the was to say about the problem then we could</font><br><font face="verdana, sans-serif">be done with it and simply write:</font><br><br><font face="monospace">DLA1 (fs, bs) = ([], fs ++ bs)</font><br><br><font face="verdana, sans-serif">However, this isn't the case. We want more from a DLA, namely its state.</font><br><font face="verdana, sans-serif">We are not just concerned with the fact </font><i style="font-family:verdana,sans-serif">that</i><font face="verdana, sans-serif"> free particles become bound,</font><br><font face="verdana, sans-serif">but with </font><i style="font-family:verdana,sans-serif">how</i><font face="verdana, sans-serif"> these particles become bound, the </font><font face="verdana, sans-serif"><i>intensional</i></font><font face="verdana, sans-serif"> content of the</font><br><font face="verdana, sans-serif">computation, its stateful nature. Further, we may concern ourselves with</font><br><font face="verdana, sans-serif">sensitivity to path-dependence, the manifested form's </font><i style="font-family:verdana,sans-serif">being</i><font face="verdana, sans-serif"> and </font><i style="font-family:verdana,sans-serif">becoming</i><br><font face="verdana, sans-serif">as a historical fact.</font><br><br><font face="verdana, sans-serif">To address these questions consider a dual interpretation. Rather than</font><br><font face="verdana, sans-serif">considering random walks on free particles, we can assign probability</font><br><font face="verdana, sans-serif">distributions to the bound particles (the surface-bound particles having</font><br><font face="verdana, sans-serif">non-zero probability). At every time step, each cell has some probability</font><br><font face="verdana, sans-serif">of <i>capturing</i> a free particle, and the collection of bound particles</font><br><font face="verdana, sans-serif">grows in this way[*]. As the surface changes, the distributions over the</font><br>entire<font face="verdana, sans-serif"> surface </font>are<font face="verdana, sans-serif"> recalculated, and from this perspective, it is clear</font><br><font face="verdana, sans-serif">that the combinatorial species determines future probabilities. To my</font><br><font face="verdana, sans-serif">mind, this treatment begs the question, "What might be gained from</font><br><font face="verdana, sans-serif">structuring the space of all possible bound states as a Poset"? In this</font><br><font face="verdana, sans-serif">interpretation, any DLA can be given <i>extensionally</i> as a path (really a</font><br><font face="verdana, sans-serif">lattice of 'evolutions satisfying boundary conditions') from some germ</font><br><font face="verdana, sans-serif">state to some final state.</font><br><br><font face="verdana, sans-serif">From a </font><i style="font-family:verdana,sans-serif">purely functional</i><font face="verdana, sans-serif"> perspective, it is natural (since Moggi) to</font><br><font face="verdana, sans-serif">structure stateful computations in terms of monads and free algebras[◻].</font><br><font face="verdana, sans-serif">There are a number of ways that monadic interpretations may arise in</font><br><font face="verdana, sans-serif">this context: The State monad to accumulate data separate from function,</font><br><font face="verdana, sans-serif">the Giry monad to structure a Markov transition system, or perhaps a</font><br><font face="verdana, sans-serif">monadic pointed space to structure the encapsulation of bound particles.</font><br><font face="verdana, sans-serif">While the first two are likely essentially-necessary, the last points to</font><br><font face="verdana, sans-serif">tempting but possibly exogenous interpretation. How does one know when</font><br>they have<font face="verdana, sans-serif"> accurately characterized the content of a theory? How does one</font><br><font face="verdana, sans-serif">know that there is nothing more to be gleaned?</font><br><br><font face="verdana, sans-serif">Jon</font><br><br></div><div class="gmail_default" style="font-family:verdana,sans-serif;font-size:small;color:#333333">[*] It is worth noting that to reach an analytically amenable form, I<br>was initially tempted to replace probability distributions by growth<br>rates over bound particles. Unfortunately, models of this type fail to<br>exhibit the symmetry breaking characteristic of DLAs. For example,<br>consider a computation beginning with a single germ, each side of which<br>is given the same probability and thus the same growth rate.</div><div class="gmail_default" style="font-family:verdana,sans-serif;font-size:small;color:#333333"><br>[◻] The relationship between the usage of monads in computer science<br>(for structuring programs or handling side-effects) and the usage of<br>monads in mathematics (for founding algebras) remains mystifying to me.<br>To my naive eye, it appears as one of those unlikely places where a thing<br>and the language for talking about the thing identify, but who knows?<br></div><div class="gmail_default" style="font-family:verdana,sans-serif;font-size:small;color:#333333"><br></div></div>
</blockquote></div>