The decidability boundary可判定性的邊界

A study in what verification can and cannot reach. To retire a shim you must prove it was doing something — run the test without it and watch it fail. But for many shims, the test passes without them. That is not a licence to delete: it means the isolated test does not exercise what the shim defends. This is the honest map of which shims can be judged alone, which cannot, and why.

一篇關於「驗證能碰到什麼、碰不到什麼」的研究。要退役一個 shim,你必須證明它有在做事 —— 拔掉它跑測試、看它失敗。但對很多 shim,拔掉它測試照樣過。那不是可以刪的許可:它代表這顆孤立測試根本沒有踩到那個 shim 防守的東西。這是一張誠實的地圖:哪些 shim 能單獨判、哪些不能、以及為什麼。

S1a · methodology study2026-07-18

The retirement test退役測試 Three arms, and the one that must fail三臂,以及那個必須失敗的

The protocol for retiring a shim onto a mechanism is a three-arm experiment:

把 shim 退役到機制的協定是一個三臂實驗:

ArmConfig設定Expected預期Proves證明
baselineshim onshim 開PASSthe known-good reference已知良好基準
controlshim off, no mechanismshim 、無機制FAILthe shim was load-bearingshim 是承重的
mechanismshim off, mechanism onshim 關、機制開PASSthe mechanism does its job機制做到了它的工作

The control arm is the whole game. If it fails, the shim mattered, and a passing mechanism arm is a genuine retirement (this is how io_db decay, DmcLatch, and AluLatch were retired — their controls fail on ppu_open_bus, 7-dmc_basics #19, and 03-immediate). But if the control passes — if the test is green with the shim removed — the experiment is inconclusive. You cannot prove a mechanism replaced something that, on this test, was doing nothing.

對照臂就是全部關鍵。它失敗,shim 就有意義,而機制臂通過就是真正的退役(io_db 衰減、DmcLatch、AluLatch 就是這樣退役的 —— 它們的對照在 ppu_open_bus7-dmc_basics #1903-immediate 上失敗)。但如果對照通過 —— 拔掉 shim 測試還是綠的 —— 實驗就無結論。你沒辦法證明機制取代了一個「在這顆測試上根本沒做事」的東西。

The data資料 Which controls actually fail哪些對照真的失敗

Every shim with a kill switch, run against its isolated test with the shim removed:

每個有 kill switch 的 shim,在它的孤立測試上拔掉 shim 跑一次:

ShimshimIsolated test孤立測試Control對照Decidable?可判?
io_db decayppu_open_bus (blargg)FAIL(3)yes → RETIRED是 → 已退役
DmcLatch7-dmc_basics (blargg)FAIL(#19)yes → PROVEN是 → 已證
AluLatch03-immediate (blargg)FAIL(1)yes → PROVEN是 → 已證
OpenBus last-byteAC OpenBusFAIL(1)
DLAC OpenBus / ppu_open_busPASS
OamBlankEdgeAC OAMCorruption / StaleSpritePASS
dot-339AC StaleSpriteShiftRegsPASS
BGSerialInAC_BGSerialIn: PASS · AC_BGSerialInReal (hunt)FAIL (0/1) on ...Real...Real 上 FAIL(0/1)yes → PROVEN是 → PROVEN
Dmc4015AbortAC Explicit/ImplicitAbortPASS
OamDmaPpuBustest_ppu_read_buffer #67 (blargg)FAIL(#67)yes → PROVEN (M4·P1)是 → PROVEN(M4·P1)
even_odd (PpuWriteDelay)10-even_odd_timing (blargg)FAIL(#3) "clock skipped too late"FAIL(#3)「clock skipped too late」yes → PROVEN (K=1); 09 undecidable是 → PROVEN(K=1);09 不可判
Dbl2007#67: PASS · double_2007_read (hunt)FAIL (CRC) on double_2007_readdouble_2007_read 上 FAIL(CRC)yes → PROVEN (M4·P1)是 → PROVEN(M4·P1)
Evidence grades — and a K=0 → K=1 correction. This sweep first ran at the K=0 boot alignment; the campaign pins K=1 (--reset-hold-extra 1 on every test), so once the baseline was re-certified (AC 141/141 + 147 146/1) the whole table was re-run at K=1 (28 arms). The re-run overturned this section's original headline — that even_odd and Dbl2007 were hc-identical spectators (shim armed, firing window never opening). At K=1: even_odd's control FAILs on 10-even_odd_timing (#3, "clock skipped too late") — the shim is load-bearing there, the M6×M3 mechanism replaces it, and even_odd is now PROVEN. Yet its other isolated test, 09-even_odd_frames, still passes without the shim. The very same shim is undecidable on one ROM and decidable on another — the thesis of this page in a single row: decidability is a property of the test, not the shim. Dbl2007's #67 control still passes (still undecidable) but is no longer bit-identical — removing the shim shifts the trajectory, so even the "spectator" reading was an alignment artifact. One methodological confession does survive the re-run: our first OamDmaPpuBus control used blargg's oam_read — which has no $4014 DMA, so the shim could never fire (a void arm); the correct #67 "DMA + PPU bus" control FAILs(#67) at K=1, so OamDmaPpuBus is decidable. Lesson banked: read the runner's recipe (K, env, per-ROM flags) before trusting any isolated score. 證據等級 —— 以及一個 K=0 → K=1 更正。這一輪最初跑在 K=0 開機對齊,而戰役協定每測釘 K=1(--reset-hold-extra 1),所以基礎重新認證後(AC 141/141 + 147 146/1)整張表在 K=1 下重跑(28 臂)。重跑推翻了本段原本的頭條 —— 說 even_odd 和 Dbl2007 是hc 逐位相同的旁觀者(shim 掛著、開火窗從沒打開)。K=1 下:even_odd 的對照在 10-even_odd_timing 上 FAIL(#3「clock skipped too late」)—— shim 在那裡承重,M6×M3 機制取代得了,even_odd 現在是 PROVEN。但它另一顆孤立測試 09-even_odd_frames,拔了 shim 仍然過。同一顆 shim 在一顆 ROM 上不可判、在另一顆上可判 —— 本頁論點濃縮成一列:可判性是測試的性質,不是 shim 的。Dbl2007 的 #67 對照仍通過(仍不可判),但不再逐位相同 —— 拔 shim 會位移軌跡,所以連「旁觀者」的說法也是對齊假象。有一個方法論自白撐過了重跑:第一版 OamDmaPpuBus 對照用了 blargg 的 oam_read —— 它沒有 $4014 DMA,shim 永遠開不了火(作廢臂);正確的 #67「DMA + PPU bus」對照在 K=1 下 FAIL(#67),所以 OamDmaPpuBus 可判。教訓入帳:信任任何孤立成績前,先讀 runner 的配方(K、env、per-ROM 旗標)。

The pattern規律 It is not blargg vs AccuracyCoin不是 blargg vs AccuracyCoin

The tempting reading is "blargg tests are decidable, AccuracyCoin's aren't." That is almost right but wrong in an instructive way: AC OpenBus is decidable (its control fails). The real distinction is deeper — does the isolated test actually exercise the scenario the shim defends?

誘人的讀法是「blargg 測試可判、AccuracyCoin 的不可判」。那差不多對,但錯得很有教育意義:AC OpenBus 可判(它的對照失敗)。真正的區別更深 —— 孤立測試有沒有真的踩到那個 shim 防守的場景?

The key insight for the project. A shim's decidability is a property of the test, not the shim. The mechanisms for the undecidable shims are all built and all bit-safe (they pass every arm, break no neighbour) — the M6×M3 phase table, the M4 transparent latch, the M4 hold. What is missing is a test that fails without them. That test exists: it is the full 141-suite run, in-suite, where these scenarios were found in the first place. Isolation was the right tool for the self-contained shims and the wrong tool for the interaction shims — and knowing which is which is itself the result. 對專案的關鍵洞見。一個 shim 的可判性是測試的性質,不是 shim 的。那些不可判 shim 的機制全都建好了、全都 bit-safe(每一臂都過、不壞鄰居)—— M6×M3 相位表、M4 透明閂鎖、M4 hold。缺的是一個「拔掉它們就失敗」的測試。那個測試存在:就是跑滿 141 顆的套內全跑,那些場景本來就是在那裡被找到的。孤立協定對自足的 shim 是對的工具、對互動的 shim 是錯的工具 —— 而知道哪個是哪個,本身就是結果。
The hunt: try a better ROM before the 8-hour suite. If decidability is a property of the test, "undecidable" is a standing invitation to look for a better test. On 2026-07-19 we did exactly that for the six undecidable shims — a handful of candidate ROMs each, chosen to actually exercise the defended scenario, run in minutes. Two crossed over: BGSerialIn → PROVEN (AccuracyCoin_BGSerialIn never discriminated it; AccuracyCoin_BGSerialInReal does — control 0/1, M6×M3 mechanism passes) and Dbl2007 → decidable (double_2007_read fails the CRC with the shim off, in seconds, where the ~2-hour test_ppu_read_buffer never did). Four survived — DL, OamBlankEdge, dot-339, Dmc4015Abort — no isolated ROM discriminated them, so those are the ones that genuinely earn the expensive in-suite run. The operational lesson: an isolated verdict is only as strong as the ROM you tested. Hunt for the discriminating ROM first; reserve the 8-hour suite for what actually needs it. 獵捕:動 8 小時套件前,先試一顆更好的 ROM。如果可判性是測試的性質,那「不可判」就是一張持續有效的邀請函:去找更好的測試。2026-07-19 我們對六顆不可判 shim 做的正是這件事 —— 每顆挑幾顆「真的會踩到防守場景」的候選 ROM,分鐘級跑完。兩顆跨了過去:BGSerialIn → PROVEN(AccuracyCoin_BGSerialIn 從沒鑑別得了它;AccuracyCoin_BGSerialInReal 可以 —— 對照 0/1、M6×M3 機制通過)、Dbl2007 → 可判(double_2007_read 拔 shim 就 CRC 失敗,只要幾秒,而 ~2 小時的 test_ppu_read_buffer 從來沒有)。四顆撐住了 —— DL、OamBlankEdge、dot-339、Dmc4015Abort —— 沒有孤立 ROM 鑑別得了它們,所以那四顆才是真正值得付出昂貴套內全跑的。操作上的一課:一個孤立判決,強度只到你測的那顆 ROM 為止。先獵鑑別 ROM;把 8 小時套件留給真正需要它的。

What this means這代表什麼 The verification frontier moves in-suite驗證前線移到套內

How the frame budget is measured — the mechanism. AccuracyCoin's design writes each sub-test's result code to a fixed CPU-RAM byte ($0400 + i) the moment that sub-test finishes. So the completion frame of test i is simply the frame byte i first goes non-zero — no screen parsing, no heuristics. AprNes (a fast reference emulator: ~20 s for the whole 141-test suite, versus the switch-level engine's ~8 h) watches all 141 result bytes every frame — that is our --ac-frame-map addition — and dumps the table (offset, addr, first_frame). Test i's window is [F(i−1), F(i)] + a small safety margin: AprNes and the switch-level engine settle into slightly different boot alignments and drift ~100 frames over the full run, so the margin absorbs it while the sequence stays identical. To confirm a shim in-suite the switch-level engine then runs from frame 0 to F(i)+margin (early-stop) — or, for a late test, resumes from a snapshot just before F(i−1) — and reads byte i: base vs shim-off, decidable iff the byte flips. Clean-resume caveat: a snapshot taken under one config is only valid to resume under another if the shim/mechanism has not fired before the resume point — a shim that fires every scanline (dot-339) bakes its effect into the snapshot, so it needs a from-scratch early-stop, not a resume. The window budgets the run; the range-run returns the verdict. 這個 frame 預算是怎麼量出來的 —— 機制。AccuracyCoin 的設計是:每個子測試一完成,就把它的結果碼寫進一個固定的 CPU-RAM byte($0400 + i)。所以第 i 題的完成幀,就是 byte i 第一次變非零那一幀 —— 不用解析畫面、不用啟發式。AprNes(快速參考模擬器:全 141 題只要 ~20 秒,對比開關級引擎的 ~8 小時)每一幀掃全部 141 個結果 byte —— 這就是我們加的 --ac-frame-map —— 然後 dump 出表(offset, addr, first_frame)。第 i 題的窗 = [F(i−1), F(i)] + 小安全值:AprNes 與開關級引擎會落進略微不同的開機對齊、整場漂移 ~100 幀,安全值吸收它,而順序完全一致。要套內確認一顆 shim,開關級引擎就從第 0 幀跑到 F(i)+margin(早停)—— 或對晚段的題,從 F(i−1) 前的快照 resume —— 讀 byte i:base vs 拔 shim,byte 翻了就是可判乾淨 resume 的但書:某配置下存的快照,要用另一配置 resume 才有效,前提是那顆 shim/機制在 resume 點之前沒開過火 —— 每條掃描線都開火的 shim(dot-339)會把效果烤進快照,所以它得從頭早停、不能 resume。窗排預算,range-run 給判決。