Invariants

Definition: Properties that do not change when a process is applied.

A very vague defintion

• Goal: Identify what stays constant during a repetitive process.

• Consequence: You can reason about the final state without executing the repetitive process.

Expanding on this: (Block quotes not implies I am quoting, I like the looks of it)
Reaching from an Initial State (InSt) to Final State (FnSt) may take an arbitrary but finite amount of time, we ought not spend all our time tracking every distinct state, instead we utilize invariants of the process to make a statement about the final state based on what is known. Simply, Invariants bridge the InSt with the FnSt without having to walkthrough every intermediate state.

Now I am curious about the existence of final state, does a problem with ill-defined final state renders invariants to be an incorrect tool? Or does it indicate that without a final state the problem has implications beyond repetive process?

To complete the above thought, I sought LLM’s help (I cannot validate its corectness ):
It’s summary states:

• When a Final State exists: Invariants are a shortcut to calculate the end result without simulating the steps (e.g., Empty Boxes problem).
• When a Final State is impossible: Invariants are a diagnostic tool to prove that a goal cannot be reached (e.g., Mutilated Chessboard).
• When a Final State does not exist (infinite loops): Invariants are a safety net to ensure the system doesn’t break while running forever (e.g., Banking software, OS).

• Functional Definition: An invariant is a mathematical bridge connecting an Initial State (InSt) to a Final State (FnSt), bypassing the need to calculate intermediate steps. It turns a dynamic, moving process into a static, solvable algebra equation.

• Method: Abstract the state into variables $\rightarrow$ Find an invariant $\rightarrow$ Use the invariant to deduce what is possible and what is impossible.

• (State After Move) = (State Before Move)

• The Problem it Solves:
  Reaching an FnSt from an InSt may take an arbitrary but finite amount of time. We ought not spend all our time tracking every distinct state change (State-Space Explosion). Instead, we utilize invariants to make a definitive statement about the final state based only on what is known at the start.

• Examples:

• Invariants example 1: The Empty Boxes Problem

---

Footnotes:

• Apparently walkthrough is a noun and walk through is the verb
• Functional definition and The problem it solves are built from my ‘Expanding on this’ part using LLM