- Execution is the process of moving from an imagined system $I$ to a real system.

- Definitions
- let $S$ be a set of all possible states
- a decision is an action that moves the system from one state to another
- $d: S_i \rightarrow S_j$
- a path is a finite set sequence of decisions
- $P = (d_1, d_2, ..., d_n)$
- if we start at $s_0$, following the path gives us some state trajectory
- $s_k = d_k(s_{k - 1})$
- i.e we apply decision k to state k - 1 to produce a new state k
- the imagined system is a constraint specification $I : S \rightarrow \{ true, false \}$
- a state s satisfies the imagined constraint iff $I(s)$ = true
- a viable path is a path whose final state satisfies the imagined constraints
- P is viable w.r.t. I iff $I(s_n)$ = true

- Axioms / Physics of Execution
- A1: Execution is the process of moving from an imagined system $I$ to a real system $s \in S$ such that $I(s)$ = true.
- A2: Reaching such an $s$ necessarily occurs by following some path $P = (d_1, d_2, ..., d_n)$
- A3: Before execution, the space of possible paths is enormous and only a small subset are viable.
- i.e. $|\{P : I(s_n) = true\}| << \{ P possible \}$
- A4: if a decision lies on no viable path, it incurs backtracking cost (possibly negligible, possibly catastrophic and everything in between)
- if partial path $(d_1, ..., d_k)$ cannot be extended to any viable path, then choosing $d_k$ produces a cost.
- A5: for execution to be possible, decisions must eventually produce observable outcomes whose distribution differ depending on whether the decisions lie on a viable or a non viable path.
- without such, there is no mechanism for detecting non-viable paths, correcting and converging on viable paths.
- hence execution will be impossible.

- Note:
- technically A3 puts us in a non-trivial system
- struggling to decide if that assumption is required
- the problem becomes uninteresting without that assumption, as random sampling should be sufficient in the trivial case for succeeding.

- Objective (success condition)
- find at least one viable path and realize its final state in the real world.

- The process of execution
- core idea:
- execution is the process of repeatedly collapsing a large decision set into a single actionable decision, applying it, and continuing until the imagined constraints are satisfied.

- step-by-step
- at every time step, the executor has to make a decision
- by A2, execution necessarily proceeds through sequential decisions
- because the path space is enormous (A3), at the beginning of each step, the executor is faced with many possible next decisions
- the executor must collapse this large option set into a single choice
- the chosen decision is applied to the current state, to produce the new state
- repeat as long as the new state doesn't satisfy the imagined constraints
- if I(s) = true, then execution has succeeded,
- otherwise, the process continues

- The problem with random / blind search
- let $P$ be the set of all possible paths
- let $V$ be the set of all viable paths
- by A3: $\mathbb |V| << \mathbb |P|$
- i.e. viable paths are a negligible fraction of all possible paths.
- under random uniform sampling over paths, the probability that a sampled path is viable is:
- Pr[path is viable] = $\frac{|V|}{|P|}$
- the expected number of samples required to hit a viable path is the inverse of this probability
- $\mathbb E[\#$ samples to first viable path] = $\frac{|P|}{|V|}$
- for any non-trivial system the ratio $\frac{|P|}{|V|}$ is enormous

- and this doesn't consider backtracking cost.
- for every sampled path that turns out to be non-viable, the executor must:
- pay some backtracking cost (drawn from some cost distribution)
- of which some of these cost might be negligible and some of it might be catastrophic.
- resample and try again

- The need for a model