<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>