終點不等於歷史 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.

例如：

+1 → -1

與：

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：

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

可用：

independent-event quotient；
run-length encoding；
state delta；
checkpoint；
semantic summary；
hash chain；
Merkle DAG；
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，但必須回答：

哪些語義要保留？
retention 多久？
是否有 external obligation？
是否可 reconstruction？
是否影響 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

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 吞沒。

參考文獻與相關工作

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