# DMSD Horizon Edition v0.4
## Task Families / Cost Laws

**日期：** 2026-09-30  
**狀態：** COMPLETE  
**基礎：** Horizon Edition v0.3 Compute Capacity Overlay

---

# 1. 這一輪真正補上的缺口

v0.3 已經有：

\[
\text{Compute Capacity}.
\]

但仍缺一個關鍵：

> **到底是哪一種 task 在吃這個 capacity？**

因為同樣：

\[
10^{100}
\]

的數值尺度，

可以是：

```text
symbolically represent
output all digits
enumerate all predecessors
test one candidate
multiply two huge integers
solve a matrix
verify a certificate
```

其成本可能差：

\[
10^{100}
\]

個數量級都不止。

所以 v0.4 正式引入：

\[
\boxed{
\text{Task Family}.
}
\]

---

# 2. Task Family

一個 task family：

\[
\boxed{
\mathcal Q
=
(
I,
W_Q,
M_Q,
IO_Q,
\mu_Q,
\Gamma_Q
)
}
\]

其中：

- \(I\)：input semantics；
- \(W_Q\)：work law；
- \(M_Q\)：memory law；
- \(IO_Q\)：I/O / output law；
- \(\mu_Q\)：work metric；
- \(\Gamma_Q\)：admission / calibration metadata。

---

# 3. Asymptotic Law 與 Runtime 必須分離

正式加入：

\[
\boxed{
\textbf{Asymptotic Law}
\neq
\textbf{Calibrated Runtime}.
}
\]

例如：

\[
W(N)=N\log\log N
\]

不能直接被當成：

> 實際 CPU instructions 就是 \(N\log\log N\)。

真正 runtime 應寫成：

\[
T
=
\mathcal C_Q(
W_Q,
M_Q,
IO_Q,
\text{hardware},
\text{implementation}
).
\]

v0.4 的 law 是：

\[
\boxed{
\text{structural coordinate}.
}
\]

---

# 4. Family A — Symbolic Representation

若 expression 有：

\[
S
\]

個 nodes，

則：

\[
W=\Theta(S),
\qquad
M=\Theta(S).
\]

例如：

\[
10^{10^{12}}
\]

若保存為：

```text
POW10(
  POW10(
    12
  )
)
```

expression size 很小。

所以：

\[
\boxed{
\text{Value Magnitude}
\neq
\text{Representation Cost}.
}
\]

---

# 5. Family B — Digit Materialization

若必須輸出：

\[
D
\]

digits，

至少：

\[
\boxed{
W=\Omega(D).
}
\]

若用 ASCII-like output：

\[
IO=\Theta(D)\text{ bytes}.
\]

因此即使生成算法無限快，

\[
10^{18}
\]

digits 本身仍需要：

\[
1\text{ EB}
\]

級輸出。

---

# 6. Family C — Linear Enumeration

訪問：

\[
N
\]

個 states：

\[
\boxed{
W=\Theta(N).
}
\]

這個 family 是所有：

```text
scan all
enumerate all
visit every element
```

的基本 reference。

---

# 7. Family D — Segmented Sieve

Eratosthenes-style structural reference：

\[
\boxed{
W
\sim
N\log\log N.
}
\]

memory 可以降成：

\[
\text{segment}
+
\text{primes}\le\sqrt N.
\]

但真正 implementation 還受：

- wheel；
- cache；
- segment size；
- SIMD；
- memory bandwidth；

強烈影響。

因此本版只把：

\[
N\log\log N
\]

當：

\[
\boxed{
\text{structural proxy}.
}
\]

---

# 8. Family E — Single-Integer Trial Division

對 prime / worst-case-like candidate：

\[
p\le\sqrt n.
\]

若只測 primes：

\[
W
\approx
\pi(\sqrt n)
\sim
\frac{\sqrt n}{\log\sqrt n}.
\]

因此：

\[
\boxed{
\log_{10}W
\approx
\frac12\log_{10}n
-
\log_{10}\log\sqrt n.
}
\]

這再次說明：

> 檢查一個 \(10^{100}\) 附近整數

和：

> 枚舉到 \(10^{100}\)

完全不同。

---

# 9. Family F — Schoolbook Multiplication

對：

\[
b
\]

bit integers：

\[
\boxed{
W=\Theta(b^2).
}
\]

這是簡單 reference，
不是大整數乘法 frontier。

---

# 10. Family G — Fast Multiplication Proxy

v0.4 註冊一個工程用 proxy：

\[
\boxed{
W_{\rm proxy}
=
b
\log_2 b
\log_2\log_2 b.
}
\]

它不是：

> 某個指定 implementation 的 exact complexity theorem。

它的用途是：

> 在 Horizon Map 上區分「quadratic」與「quasilinear-like」成長形狀。

---

# 11. Family H — Modular Exponentiation

如果 modulus 是：

\[
b
\]

bits，

exponent bit length：

\[
e_b,
\]

則 repeated squaring 類結構：

\[
\boxed{
W
\approx
M(b)e_b.
}
\]

其中：

\[
M(b)
\]

是註冊的 multiplication model。

因此同一個 modular task 可以切換：

```text
schoolbook multiplication plugin
fast multiplication plugin
hardware-specific plugin
```

---

# 12. Family I — Dense Matrix Multiplication

Classical dense \(n\times n\)：

\[
\boxed{
W\approx2n^3
}
\]

floating operations。

Resident A/B/C memory：

\[
\Theta(n^2).
\]

這是一個非常好的 compute-vs-memory Horizon 測試。

---

# 13. Family J — Dense LU

factorization core：

\[
\boxed{
W\approx\frac23n^3
}
\]

floating operations。

memory：

\[
\Theta(n^2).
\]

所以 matrix dimension horizon 同時受：

- FLOPS；
- memory capacity；
- bandwidth；

限制。

---

# 14. Family K — Graph Traversal

BFS / DFS-like structural model：

\[
\boxed{
W=\Theta(V+E).
}
\]

如果 graph 本身不能 fit memory，

compute throughput 再高也沒用。

因此 graph horizon 是：

\[
\boxed{
\text{memory-sensitive}.
}
\]

---

# 15. Family L — Monte Carlo

若：

\[
S
\]

samples，

每個 sample：

\[
C
\]

work，

則：

\[
\boxed{
W=SC.
}
\]

如果 samples truly independent，
parallel efficiency 可能很高。

所以同樣 work size：

\[
10^{18}
\]

如果 task topology 不同，
distributed horizon 也不同。

---

# 16. Family M — Certificate Verification

generic reference：

\[
W=\Theta(C)
\]

其中：

\[
C
\]

是 certificate size / local-check units。

但真正 certificate family 必須可 override。

例如：

```text
Pratt
SNARK-like
proof trace
formal kernel proof
SAT certificate
```

全部可以成獨立 plugin。

---

# 17. 為什麼 Prime Counting 沒直接塞一條神奇公式

因為：

```text
sieve-based counting
combinatorial prime counting
Lagarias–Miller–Odlyzko-like methods
Deleglise–Rivat variants
primecount-specific algorithms
```

不是同一個 law。

所以 v0.4 故意只註冊：

\[
\boxed{
\text{segmented-sieve counting reference}.
}
\]

更進階方法應該：

\[
\boxed{
\text{register as algorithm plugins}.
}
\]

這避免「prime counting complexity」被粗暴壓成一條假公式。

---

# 18. Log-Space Cost Evaluation

普通 cost calculator 在：

\[
N=10^{10^{12}}
\]

會直接 overflow。

所以 v0.4 的 reference evaluator 不先算：

\[
N.
\]

而保存：

\[
\boxed{
\log_{10}N.
}
\]

並直接輸出：

\[
\log_{10}W.
\]

例如 linear：

\[
\log_{10}W
=
\log_{10}N.
\]

power：

\[
W=N^\alpha
\]

則：

\[
\log_{10}W
=
\alpha\log_{10}N.
\]

---

# 19. Horizon Map 因此可以超越浮點數

只要 law 可以在 log-space 計算，

就可以對：

\[
10^{1000}
\]

甚至更高 finite exponent
估：

\[
\log_{10}W.
\]

若連 exponent 都是 symbolic：

\[
10^{10^{12}},
\]

就保持 symbolic law：

\[
W_Q(
10^{10^{12}}
).
\]

不強迫轉成 IEEE float。

---

# 20. 同一 Scale 的 Task Split

例如：

\[
N=10^{18}.
\]

### Symbolic reference

如果只是保存：

```text
10^18
```

成本接近常數 / expression size。

### Enumerate

\[
W\sim10^{18}.
\]

### Sieve

\[
W\sim
10^{18}\log\log10^{18}.
\]

### Trial-divide one \(10^{18}\) candidate

只需走到：

\[
10^9
\]

附近 divisor scale。

所以：

\[
\boxed{
\text{Horizon}
}
\]

永遠必須附 task label。

---

# 21. Multiplication Example

對：

\[
10^9
\]

bit integers：

schoolbook：

\[
\log_{10}W=18.
\]

fast proxy 大約：

\[
b\log b\log\log b,
\]

會遠低於：

\[
b^2.
\]

所以未來巨大 integer horizon
會高度依賴 algorithm family。

---

# 22. Matrix Example

若：

\[
n=10^6,
\]

classical matmul：

\[
W
\approx
2\times10^{18}
\]

FLOPs。

LU：

\[
W
\approx
6.67\times10^{17}.
\]

但 matrix storage 本身已經是：

\[
10^{12}
\]

elements。

若 8-byte values：

\[
8\text{ TB}
\]

per matrix。

所以 workstation FLOPS 再高：

\[
\boxed{
\text{memory gate comes first}.
}
\]

---

# 23. Cost Law Registry

v0.4 的 task registry 對每個 family 保存：

```text
task_id
input semantics
work metric
law
model
memory law
IO law
notes
```

未來新算法：

> 不改 Horizon Core。

只新增：

\[
\boxed{
\text{Cost-Law Plugin}.
}
\]

---

# 24. Calibration Layer

v0.5 以前先不把 calibration 塞進 core。

之後可以為：

\[
Q
\]

增加：

\[
\kappa_Q(
\text{hardware},
\text{implementation},
\text{size}
).
\]

最後 runtime：

\[
T_Q
=
\kappa_Q
\cdot
\frac{W_Q}{F_Q}.
\]

這樣：

\[
\boxed{
\text{theory law}
}
\]

與：

\[
\boxed{
\text{empirical benchmark}
}
\]

保持分離。

---

# 25. Validation

v0.4 對 cost laws 做：

```text
2500 one-parameter monotonic checks
750 two-parameter monotonic checks
500 output-lower-bound checks
multiplication growth cross-checks
```

全部 PASS。

檢查的是：

- 尺度增大不能讓 structural work 反而下降；
- output digits 與最低 output work 一致；
- quasilinear proxy 在足夠大 bit length 下低於 quadratic schoolbook。

---

# 26. 現在 Horizon Edition 有三層

## Scale Layer

\[
\boxed{
\text{Where?}
}
\]

## Task Layer

\[
\boxed{
\text{What are you doing there?}
}
\]

## Capacity Layer

\[
\boxed{
\text{What resources execute it?}
}
\]

所以完整投影：

\[
\boxed{
\text{Scale}
\rightarrow
\text{Task Law}
\rightarrow
\text{Capacity}
\rightarrow
\text{Time/Memory/IO/Energy}.
}
\]

---

# 27. 下一步

最自然的下一輪：

# Horizon Edition v0.5 — Algorithm Plugin + Calibration Layer

選幾個真正實作：

- segmented prime sieve；
- big integer multiplication；
- dense GEMM；
- certificate verification；

在本地做 size sweep，
量：

```text
wall-clock
memory
effective throughput
scaling exponent
```

再把：

\[
W_Q(n)
\]

和 empirical：

\[
T_Q(n)
\]

接起來。

這樣 Horizon Edition 就不只是 asymptotic map，
而開始有：

\[
\boxed{
\text{measured cost surface}.
}
\]

---

# 28. 結論

v0.4 最重要的不是多列幾個 Big-O。

而是把：

\[
\boxed{
\text{Scale}
}
\]

和：

\[
\boxed{
\text{Task}
}
\]

正式拆開。

所以「人類能算到多大」現在不再是：

\[
10^N?
\]

而是：

\[
\boxed{
H(Q,A,C,B)
}
\]

其中：

- \(Q\)：task；
- \(A\)：algorithm；
- \(C\)：capacity；
- \(B\)：resource budget。

---

```text
DMSD Horizon Edition v0.4: COMPLETE
Task Families: REGISTERED
Log-space Cost Evaluator: PASS
Next:
Algorithm Plugin + Calibration Layer
```