state
Last edited: August 8, 2025Lambda Calculus with state:
\begin{equation} e \to (x | \lambda x . e | e e | i | \text{new} | {!e} | e := e) \end{equation}
where:
- \(new\) allocate a new memory location \(x\) and return pointer (initialize \(x\) to \(0\))
- \(!e\) deref a pointer
- \(e := e\), which is assigning the pointee of the memory location at the first argument to the second argument
new
\begin{equation} \frac{l \not \in dom(S)}{E,S \vdash \text{new} \to l, S[l=0]} \end{equation}
stationary-action principle
Last edited: August 8, 2025The stationary-action principle states that, in a dynamic system, the equations of motion of that system is yielded as the “stationary points” of the system’s action. i.e. the points of “least” action. (i.e. a ball sliding down a ramp is nice, but you don’t expect it—in that system—to fly off the ramp, do a turn, and then fly down.
STCONN
Last edited: August 8, 2025\begin{equation} \text{STCONN} = \qty {\langle G, S, t \rangle : \text{$\exists^{?}$ a path from s $\to$ t $\in$ G}} \end{equation}
we solve this with BFS or DFS; but those algorithms’ working sets require linear space. Turns out, we can solve this algorithm \(\text{STCONN} \in \text{SPACE}\qty(\log^{2}\qty(n))\)
open problem: Savitch’s Algorithm is really really slow; we are not sure if there is an algorithm in which we can solve it in better time.
Stepwise Evolution
Last edited: August 8, 2025To put some math behind that very, extremely simple Dyson’s Model, we will declare a vector space \(K\) which encodes the possible set of states that our “cell” can be in. Now, declare a transition matrix \(M \in \mathcal{L}(K)\) which maps from one state to another.
Finally, then, we can define a function \(P(k)\) for the \(k\) th state of our cell.
That is, then:
\begin{equation} P(k+1) = M P(k) \end{equation}
(as the “next” state is simply \(M\) applied onto the previous state).
