Geometry, sweep, simulation, and parsing · HTML
state_{t+1}=F(state_t,input_t); output comes from state or transition; repetition of a complete deterministic finite state repeats the future.
Recognition signals
- The specification is an explicit stepwise process
- Each step depends on small current state
- Rule branches are precise
- A final configuration or step count is requested
- Repeated states and cycles may appear
False friends
| Signal | Why it is different |
|---|
| A direct aggregate formula exists | If steps commute or have a closed form, literal simulation may time out. |
| Recorded state omits history that affects the future | If equal recorded states can diverge later, the state is not sufficient. |
Core invariant
At loop entry, state completely describes the real process configuration, and one transition is definitionally equivalent to one rule step.
State, transition, and processing order
| Item | Definition |
|---|
| State | Only future-relevant fields such as position, direction, mode, and counters; optionally seen[state]=(step,metric). |
| Transition | Read the old state and input, apply mutually exclusive rule priority, and fast-forward only after a complete state repeats. |
| Frontier / order | step separates an exactly executed prefix from the remaining suffix; fast-forward skips only whole identical cycles. |
Python skeleton
def run_machine(initial, steps, transition):
state = initial
seen = {}
t = 0
while t < steps:
if state in seen:
cycle = t - seen[state]
if cycle:
jump = (steps - t) // cycle
if jump:
t += jump * cycle
continue
else:
seen[state] = t
state = transition(state)
t += 1
return state
Correctness sketch
- The initial state matches the real initial configuration.
- If the current state is correct, an equivalent transition produces the correct next state.
- Induction proves every explicitly executed prefix.
- A deterministic system returning to the same complete state has the same future, so whole-cycle jumps preserve the final state.
Complexity
| Time | Space | Parameters |
|---|
| O(T) directly; cycle acceleration often O(S) for finite state | O(1) directly or O(S) with seen | T requested steps and S reachable states |
Edge cases
- steps=0 returns the initial state
- Conflicting rule priority
- Synchronous updates must not observe partial new state
- Cycle keys must be hashable
- A remainder shorter than one cycle still runs
Error patterns
| Pattern | Why it fails / fix |
|---|
| In-place synchronous updates | Compute all new fields from the old snapshot. |
| Cycle detection on incomplete state | Omitted direction or phase causes invalid jumps. |
| Jumping past the remainder | Only complete cycles may be skipped. |
Selection and exclusion rules
- Affordable step count: direct simulation is clearest.
- Huge T and finite state: record first occurrence and detect cycles.
- Multiple synchronous entities: build next_state, then replace.
- Look for algebraic aggregation before committing to every step.
| Relation | Template | Boundary |
|---|
| finite-state complement | Stack-based state simulation | Use enum states for flat phases and frame stacks for nesting. |
| optimization-branch contrast | Finite-state-machine DP | Upgrade to DP when several reachable modes aggregate an optimum or count; deterministic single-successor processes need only simulation |
Original micro-example
| Part | Detail |
|---|
| Result | The length-two cycle 1↔3 enables fast-forwarding. |
| Scenario | States follow 0→1→3→1 for ten steps. |
| Walkthrough | On revisiting complete state 1, the future is fixed; only the final step-count remainder needs explicit execution. |
Recall prompts
My notes