# 終點不等於歷史 v0.1
## 非交換計算序列、世界狀態與可追溯全域演化

**Endpoint Is Not History v0.1: Noncommutative Computational Sequences, World State, and Traceable Global Evolution**

- 編號：EML-GCM-2026-06-v0.1
- 日期：2026-08-23
- 作者：Neo.K
- 協作：Aletheia / GPT
- 狀態：核心理論論文 / History–State 分離
- 邊界聲明：本文不宣稱所有不同歷史都必須永久保存，也不宣稱所有 schedule difference 都具有語義差異；歷史等價關係必須由明確 independence / observation / invariant 條件定義。

---

## 摘要

計算系統常以「目前狀態」作為主要對象：如果兩條執行最後得到同一 state，工程上往往傾向將它們視為等價。然而在存在非交換操作、併發、交易、資源競爭、觀察者、錯誤恢復與法律／因果稽核的世界中，終點相同並不足以保證歷史相同。

本文提出：

$$
\boxed{
\text{State Equality}
\not\Rightarrow
\text{History Equality}
}
$$

以及：

$$
\boxed{
\text{Endpoint Closure}
\neq
\text{History Closure}.
}
$$

本文把全域計算 Runtime 擴張為 state 與 history 雙軌系統。令：

$$
W_{t+1}
=
\Phi_{a_t}(W_t)
$$

而 execution history：

$$
H_t
=
(a_0,a_1,\ldots,a_{t-1})
$$

或更一般的 partial-order event structure。當操作不交換：

$$
\Phi_a\circ\Phi_b
\neq
\Phi_b\circ\Phi_a,
$$

schedule 本身就是語義的一部分。

本文同時引入 independence relation、history quotient、Mazurkiewicz-trace-like equivalence、receipt DAG、causal dependency 與 observable-history equivalence，主張 Runtime 不應保存所有排列，而應保存足以區分有語義差異的歷史結構。

---

# 1. 終點狀態的誘惑

對 deterministic state machine：

$$
s_{t+1}=f(s_t,a_t),
$$

常見做法是只保存：

$$
s_t.
$$

若系統可從 state 完整繼續，這很有效。

但若需要回答：

- 為什麼到這裡？
- 哪個 operation 先發生？
- 哪個 agent 寫入？
- 哪個 solver 被切換？
- 哪次失敗被 rollback？
- 哪個 observation 影響 decision？
- 哪個 resource migration 發生？

state alone 不夠。

---

# 2. History

最簡單定義：

$$
H_t
=
(a_0,a_1,\ldots,a_{t-1}).
$$

世界：

$$
W_t
=
\Phi_{a_{t-1}}
\circ\cdots\circ
\Phi_{a_0}
(W_0).
$$

所以：

$$
W_t
=
F(W_0,H_t).
$$

但反向一般不是唯一：

$$
W_t
\not\Rightarrow
H_t.
$$

---

# 3. State Equality 不推出 History Equality

可能：

$$
F(W_0,H_1)
=
F(W_0,H_2)
$$

但：

$$
H_1\neq H_2.
$$

例如：

```text
+1 → -1
```

與：

```text
identity
```

終點可能相同，但前者發生過兩個 event。

因此：

$$
\boxed{
\text{same endpoint}
\neq
\text{same process}.
}
$$

---

# 4. 非交換性

若：

$$
\Phi_a\Phi_b
\neq
\Phi_b\Phi_a,
$$

則 order 直接改變 endpoint。

這是最明顯的 history sensitivity。

例：

$$
a:\ x\mapsto 2x
$$

$$
b:\ x\mapsto x+1.
$$

則：

$$
b(a(x))=2x+1
$$

而：

$$
a(b(x))=2x+2.
$$

所以：

$$
[a,b]\neq0.
$$

---

# 5. 交換不代表歷史無意義

即使：

$$
\Phi_a\Phi_b
=
\Phi_b\Phi_a,
$$

歷史仍可能因：

- timestamp；
- cost；
- resource；
- authorization；
- observer；
- external side effects；
- failure；
- provenance；

而不同。

因此 algebraic commutativity 只是 history quotient 的一個條件，不是全部。

---

# 6. Schedule Explosion

對 $n$ 個可排序 events，最壞排列：

$$
n!.
$$

若每一種 order 都保存，歷史空間迅速爆炸。

DGW 之前的有限 heterogeneous noncommutative spike 已展示一種更一般現象：即使 global endpoint state space 很小，合法 schedule 數仍可極大。

因此：

$$
\boxed{
\text{Finite Global State Closure}
\neq
\text{Finite Manageable History Space}.
}
$$

---

# 7. Endpoint Compression 的危險

若只以：

$$
hash(W_t)
$$

去重所有執行，

會把：

$$
H_1,H_2
$$

在 endpoint 相同時合併。

這只有在我們已證明：

$$
H_1\sim H_2
$$

對目標語義等價時才安全。

否則是錯誤 history quotient。

---

# 8. Independence Relation

借用 trace theory 的基本精神，定義 events：

$$
\Sigma
$$

與 independence：

$$
I
\subseteq
\Sigma\times\Sigma.
$$

若：

$$
(a,b)\in I,
$$

表示相鄰交換：

$$
\alpha ab\beta
\sim
\alpha ba\beta
$$

不改變我們關心的語義。

注意：

$$
I
$$

不是固定由「不同 thread」決定，而應由 domain、shared state、observer 與 invariants 共同定義。

---

# 9. Dependence Relation

定義：

$$
D
=
(\Sigma\times\Sigma)\setminus I.
$$

若：

$$
(a,b)\in D,
$$

則 order 必須保留。

因此 history 可由 full sequence 壓縮成 dependent-event partial order。

---

# 10. Trace Equivalence

令：

$$
H_1\equiv_I H_2
$$

當且僅當可透過有限次交換相鄰 independent events 從 $H_1$ 變成 $H_2$。

這類 equivalence 與 Mazurkiewicz trace theory 的精神一致。

因此 Runtime 不一定保存每一個 permutation，只需保存 equivalence class 或 representative。

---

# 11. 但 Observer 會改變 Independence

一個 event 的值若從未被任何後續操作 observe，某些 write order 可能對程式可見行為無差。

但如果未來有 observer：

$$
o
$$

讀取該值，

依賴就出現。

所以：

$$
I
=
I(H,O,C)
$$

可能是 context-dependent。

這與「Optimal DPOR with Observers」等研究中的 observer-dependent interference 有概念對照。

---

# 12. History Relative to Semantics

不能問：

> 兩條歷史是否「絕對等價」？

應問：

$$
H_1
\sim_{\mathcal S}
H_2
$$

其中 $\mathcal S$ 是所關心的 semantics：

- endpoint state；
- safety；
- visible outputs；
- cost；
- legal provenance；
- causal structure；
- user experience。

不同 $\mathcal S$ 產生不同 quotient。

---

# 13. Endpoint Semantics

若只關心 endpoint：

$$
H_1
\sim_E
H_2
\iff
F(W_0,H_1)=F(W_0,H_2).
$$

這是最粗的 equivalence。

但它丟失最多資訊。

---

# 14. Observable Semantics

給 Observer：

$$
\Pi_O.
$$

定義：

$$
H_1
\sim_O
H_2
$$

若所有相關 observation 相同。

即使 endpoint state 不同，也可能對某 Observer indistinguishable。

---

# 15. Causal Semantics

定義事件 DAG：

$$
G_H=(E,\prec).
$$

其中：

$$
e_i\prec e_j
$$

表示 $e_j$ causally depends on $e_i$。

若兩條 full schedule 具有相同 causal partial order，可在某些語義下視為同一 history class。

---

# 16. Receipt

每一個 world-changing operation 建立 receipt：

$$
R_k
=
\langle
id,
parent,
domain,
op,
input,
output,
prestate,
poststate,
constraint,
resource,
time
\rangle.
$$

History：

$$
\mathcal H_t
=
\{R_0,\ldots,R_{t-1}\}.
$$

---

# 17. Receipt DAG

若 operations 並行，receipt 不應硬壓成單一 total order。

建立：

$$
G_R
=
(V_R,E_R).
$$

edge：

$$
R_i\to R_j
$$

表示 dependency。

因此：

$$
\boxed{
\text{History}
=
\text{partially ordered event structure}
}
$$

通常比單一 log sequence 更準確。

---

# 18. Total Order 是一種 Presentation

即使 storage 用 append-only log：

$$
R_0,R_1,\ldots
$$

也不代表世界因果真的全序。

Total order 可以只是 serialization。

因此：

$$
\boxed{
\text{Log Order}
\neq
\text{Causal Order}
}
$$

一般而言。

---

# 19. Causal Consistency

Distributed systems 長期研究 causal consistency 與 happens-before。

GCM 的 history layer 可借用：

$$
\prec_{causal}.
$$

若兩個 events 不存在 causal dependency：

$$
e_i\parallel e_j,
$$

Runtime 可允許 reorder / parallel execution。

---

# 20. Noncommutative History

若：

$$
e_i\not\parallel e_j,
$$

順序保留：

$$
e_i\prec e_j.
$$

因此真正需要保存的是：

$$
\boxed{
\text{dependent order}
}
$$

而不是所有無關 permutation。

---

# 21. History Closure

State space closure：

$$
|\mathcal W|<\infty
$$

不推出 history closure：

$$
|\mathcal H|<\infty.
$$

即使有限 state machine 有 loop：

$$
s_0\to s_1\to s_0\to\cdots
$$

history length 仍無界。

所以：

$$
\boxed{
\text{Endpoint Closure}
\neq
\text{History Closure}.
}
$$

---

# 22. Loop Quotient

如果 repeated loop：

$$
L^k
$$

只關心 endpoint，

可壓：

$$
(k,L).
$$

若關心每次 loop cost：

$$
\{cost_1,\ldots,cost_k\}
$$

則不能只存 $k$。

所以 compression schema 依 semantics 決定。

---

# 23. Checkpoint + Delta

不需永久保存每個 full state。

可：

$$
Checkpoint_j
+
\Delta H_{j\to t}.
$$

因此 reconstruct：

$$
W_t
=
Replay(Checkpoint_j,\Delta H).
$$

這是 history storage 與 active memory 的橋。

---

# 24. Event Sourcing 類比

Event-sourced system 通常以 events 作 canonical log，再重建 state。

GCM 不強迫 event log 必須是唯一真實層，但接受：

$$
\boxed{
\text{State}
\leftrightarrow
\text{Checkpointed Projection of History}
}
$$

作為一種 Runtime strategy。

---

# 25. Undo 不等於刪除 History

若：

$$
a
$$

之後：

$$
a^{-1},
$$

回到：

$$
W_0,
$$

也不應把：

$$
[a,a^{-1}]
$$

當成從未發生。

因此：

$$
\boxed{
\text{Undo}
\neq
\text{Erase History}.
}
$$

對 audit、安全、因果分析尤其重要。

---

# 26. Retry

失敗後 retry：

```text
attempt 1: fail
attempt 2: succeed
```

endpoint 與一次成功相同，但 reliability history 不同。

所以 receipt 應保留 failure events。

---

# 27. Speculative Execution

若 speculative branch：

$$
H_a,H_b,H_c
$$

最後 commit $H_b$，

其他 branch 可標：

$$
aborted
$$

而不必從歷史完全消失。

這對 debugging / learning router 有價值。

---

# 28. Configuration Switching History

若 computational form：

$$
c_a\to c_b,
$$

即使 world state representation 等價，切換本身也有：

- bridge cost；
- approximation；
- reason；
- model version。

所以：

$$
SwitchReceipt
$$

應屬於 history。

---

# 29. Observer History

Observer-only operation 不改 World，但可以有 observer history：

$$
H_O.
$$

例如：

- focus；
- zoom；
- query；
- inspection。

因此：

$$
H_W
\neq
H_O.
$$

如果 Observer action 觸發 world-changing command，再建立 causal edge：

$$
R_O\to R_W.
$$

---

# 30. World Boundary 與 History Boundary

對 sub-world $W_i$，它可以有 local history：

$$
H_i.
$$

parent world 保存 summary pointer：

$$
h_i^{summary}.
$$

因此 recursive world 不必把所有 descendant logs flatten 成一個巨大 total order。

---

# 31. History Compression

可用：

1. independent-event quotient；
2. run-length encoding；
3. state delta；
4. checkpoint；
5. semantic summary；
6. hash chain；
7. Merkle DAG；
8. external archive。

但 compression 必須保留目標 invariants。

---

# 32. Hash 不等於 History

兩條 history 的 hash 可用來 identifier，但：

$$
hash(H)
$$

不是 history semantics。

Hash 只能證明 identity/integrity，不能解釋 causal structure。

---

# 33. Versioned World

每次 commit：

$$
W^{(v)}
\to
W^{(v+1)}.
$$

Receipt：

$$
R_v:
W^{(v)}
\to
W^{(v+1)}.
$$

這與 foundation revision：

$$
\mathcal A^{(v)}
\to
\mathcal A^{(v+1)}
$$

的 versioned principle 相容。

---

# 34. Foundation History 與 Runtime History

要區分：

## Runtime history

world state 內的 operation history。

## Foundation history

axiom/schema/runtime contract 的版本變更。

Foundation revision 必須 explicit，不能由普通 Runtime 自動偷偷改 axioms。

---

# 35. Schedule as State?

可把 scheduler internal state：

$$
S_t^{sched}
$$

納入 Runtime state。

但仍不能因此把歷史完全消掉，因為 scheduler state 是 history compression，不一定可逆。

---

# 36. History-aware Routing

Router 可以使用：

$$
\mathcal R_t
=
R(W_t,H_t,Q_t).
$$

例如：

- 避免剛失敗的 accelerator；
- 避免 thrashing；
- 根據 previous bridge error；
- 根據 past latency；
- 根據 provenance。

所以 history 不只為 audit，也能改變未來 routing。

---

# 37. Path-dependent System

若：

$$
W_{t+1}
=
F(W_t,H_t,a_t),
$$

則系統 path-dependent。

例如：

- hysteresis；
- fatigue；
- learning；
- cache；
- trust；
- reputation；
- adaptive basis memory。

這些系統不能只用當前表面 state 解釋全部未來。

---

# 38. History State Variable

可以壓縮歷史成：

$$
z_t
=
\Psi(H_t).
$$

世界：

$$
W_{t+1}
=
F(W_t,z_t,a_t).
$$

 $z_t$ 是 history state variable。

若 $\Psi$ sufficient，則不需讀全 log。

---

# 39. Markovization

某些 non-Markov process 可以透過擴大 state：

$$
\tilde W_t=(W_t,z_t)
$$

變成 Markov-like。

但代價是：

$$
dim(\tilde W)>dim(W).
$$

這是一種 history compression，而不是歷史不存在。

---

# 40. History Sufficiency

若：

$$
P(W_{t+1}|H_t)
=
P(W_{t+1}|z_t),
$$

則 $z_t$ 對下一步是 sufficient summary。

但對 audit 可能仍不足。

因此：

$$
\boxed{
\text{Predictive Sufficiency}
\neq
\text{Audit Sufficiency}.
}
$$

---

# 41. 可刪除歷史

Runtime 可以依 policy 刪除或壓縮 history，但必須回答：

1. 哪些語義要保留？
2. retention 多久？
3. 是否有 external obligation？
4. 是否可 reconstruction？
5. 是否影響 future routing？

所以：

$$
Delete(H)
$$

本身也是 policy decision。

---

# 42. Privacy

History 越完整，privacy risk 越高。

因此 provenance 必須與：

- minimization；
- access control；
- encryption；
- retention；

共同設計。

本文不主張「永遠保存所有歷史」。

---

# 43. History Quotient 的一般形式

給定 semantics：

$$
\mathcal S,
$$

定義：

$$
H_1
\sim_{\mathcal S}
H_2
\iff
\operatorname{Obs}_{\mathcal S}(H_1)
=
\operatorname{Obs}_{\mathcal S}(H_2).
$$

Runtime 可保存 equivalence class：

$$
[H]_{\mathcal S}.
$$

---

# 44. 多重 Quotient

同一 history 可同時有：

- endpoint quotient；
- safety quotient；
- cost quotient；
- provenance quotient；
- observer quotient。

所以不能期待一個 universal compressed history。

---

# 45. Partial Order Reduction 的啟示

Model checking 使用 partial order reduction，透過 independent actions 的交換等價避免探索所有 interleavings。

這與本文的核心需求高度相關：

$$
\boxed{
\text{Do not preserve every permutation;
preserve every semantically distinct dependency structure}.
}
$$

---

# 46. 但 Runtime 與 Model Checking 不同

Model checking 的目標是探索足夠 executions 驗證 property。

Runtime history 的目標可能是：

- replay；
- audit；
- future routing；
- debugging；
- legal provenance；
- learning。

因此 equivalence relation 可能不同。

---

# 47. 歷史爆炸的控制

最小方法：

$$
H
\to
\{
checkpoint,
dependency\ DAG,
receipts,
summaries
\}.
$$

而不是：

$$
H
\to
\text{all possible schedules}.
$$

Runtime 只保存 actual execution + necessary alternatives/metadata。

---

# 48. Counterfactual History

AI planning 可能生成：

$$
H^{cf}_1,\ldots,H^{cf}_n.
$$

這些是 counterfactual，不是 committed history。

必須標：

$$
status\in\{speculative,committed,aborted\}.
$$

否則會污染 provenance。

---

# 49. World History 與 Model History

模型可能更新：

$$
M^{(v)}
\to
M^{(v+1)}.
$$

同一 world event 用不同 model 解釋會不同。

因此 receipt 應記：

$$
model\_version.
$$

---

# 50. 可實驗命題

### 命題 A

在含獨立 operations 的 concurrent workload 中，以 dependence partial order 取代 full total-order permutations，可顯著壓縮 history classes。

### 命題 B

若錯誤地把 observer-dependent operations 判為 independent，history quotient 可能破壞 observable behavior。

### 命題 C

endpoint-only dedup 在有 retry/rollback/provenance requirement 的系統中不足。

### 命題 D

history-aware routing 可減少 repeated failure 或 configuration thrashing。

---

# 51. 最小 Runtime History Algorithm

```pseudo
on operation proposal op:
    deps = detect_dependencies(op, active_receipts)

    execute op

    if commit:
        receipt = {
            op,
            pre_version,
            post_version,
            dependencies = deps,
            resource,
            form,
            law,
            cost,
            result
        }

        append receipt
        update dependency DAG
        update history summary z_t

periodically:
    checkpoint world
    quotient/archive old receipts
    preserve required causal/provenance structure
```

---

# 52. 核心不變量

### Invariant 1

每個 committed world transition 都有 receipt 或明確 exempt reason。

### Invariant 2

Dependency edge 不得指向不存在的 parent receipt。

### Invariant 3

Rollback 不刪除已發生 receipt，只新增 inverse/rollback receipt。

### Invariant 4

Observer-only history 與 world mutation history 分層。

### Invariant 5

History compression 不得破壞指定 semantics $\mathcal S$。

---

# 53. 最終定義

本文把「可追溯全域演化」定義為：

> 全域 Runtime 不只保存可執行的當前 world state，也保存或可重建足以區分語義相關 execution histories 的事件依賴結構，使非交換順序、因果依賴、配置切換、失敗與回復不會因 endpoint state 相同而被無條件消失。

形式化核心：

$$
\boxed{
W_t
\text{ and }
[H_t]_{\mathcal S}
}
$$

共同構成可追溯 Runtime state。

---

# 54. 結論

終點狀態是一種壓縮。

歷史則是過程。

很多時候壓縮足夠，但不能把壓縮結果誤認為所有過程都等價。

所以：

$$
\boxed{
\text{State Equality}
\not\Rightarrow
\text{History Equality}
}
$$

以及：

$$
\boxed{
\text{Endpoint Closure}
\neq
\text{History Closure}.
}
$$

真正可擴展的方法不是保存所有 schedule，而是建立：

$$
\boxed{
\text{Dependency}
+
\text{Equivalence}
+
\text{Receipt}
+
\text{Checkpoint}
+
\text{Semantic Quotient}.
}
$$

這讓全域計算既能保留非交換歷史，又不被 combinatorial history space 吞沒。

---

## 參考文獻與相關工作

1. Mazurkiewicz trace theory and classical concurrency literature.
2. Diekert, V. *Combinatorics on Traces*. 1990.
3. *Optimal Dynamic Partial Order Reduction with Observers*. TACAS, 2018.
4. *Quasi-Optimal Partial Order Reduction*. CAV, 2018.
5. *Parsimonious Optimal Dynamic Partial Order Reduction*. 2024.
6. *Extracting safe thread schedules from incomplete model checking results*. 2020.
7. Event structures, partial-order semantics, causal consistency, and distributed provenance literature.