期限，而非停機

有限基板與有限觀測下的停機問題

Deadlines, Not Halting: The Halting Problem under Finite Substrate and Finite Observation

作者：Neo.K (許筌崴) 機構：EveMissLab (一言諾科技有限公司) **日期：2026年6月

摘要

停機問題作為一條數學定理是無條件成立的，但它陳述的對象是一個理想化物件：一台資源無界的機器，被一個耐心無限的觀察者審視。本文主張，這條定理的「咬合力」完全來自這兩個無限，而現實世界一個都不提供。把無限從機器那側拿掉（有限基板），不可判定性退化為可判定但不可行；把無限從觀察者那側拿掉（有限觀測窗），那個可判定但精細的區分，進一步被壓平成一個粗糙、二值、卻人人都讀得懂的判決：「在我等的時間內給了答案，或沒給」。後者一桶裝下了慢、循環、崩潰、與基板死亡。本文把這個現象稱為停機問題對任何觀察者的「雙重隔開」——一次被物理隔開，一次被認識論隔開——並論證：這個壓平對觀察者算力近乎不變，更強的觀察者只能把期限往外推、把可證終止的典型多數判得更細，卻動不了那個對抗性的不可判定核。最後，本文以動力系統作為詮釋層，指出停機問題、同步崩潰、與混沌不可預測，是同一個分岔的不同名字。

關鍵詞：停機問題、可計算性、物理計算極限、Landauer 原理、觀察者相對性、動力系統、不可判定性

1. 引言：定理與現實之間的落差

停機問題說：不存在一個通用程序，能對任意「程式＋輸入」判定它最終會不會停。這是 Turing 在 1936 年證明的，它不可被任何實驗推翻，在任何宇宙都成立。然而每一個寫過程式的人都知道，當一台機器「不給答案」時，他不會去追問「這是一個第二型不可判定實例嗎」——他會說「當機了」，然後重啟。

定理的莊嚴與現實的隨便之間，存在一道落差。本文的論點是：這道落差不是現實的粗糙，而是定理的精確——停機問題精確地只在一個沒有人坐得進去的座位上成立。那個座位需要兩樣現實不提供的東西：一台永遠不耗盡、不衰變的機器，和一個願意永遠等下去的觀察者。把這兩個無限分別拿掉，定理會以兩種不同的方式退場。本文依序處理這兩次退場，並論證它們合起來，把「停機」這個概念對任何有限存在者，重寫成「期限」。

2. 兩種停機

必須先把一個被日常語言混淆的區分劃開：抽象計算的停機，與物理基板的停機，是兩件事。

在 Turing 的模型裡，機器有無界紙帶、離散步、無時間上限、無物理衰變。「停機」是一個離散事件：控制狀態抵達指定的停機態。「不停機」是它的補集：永遠運轉而不抵達該態。這是一個關於抽象軌跡的性質，與任何金屬、矽、或能量無關。

物理基板則從不在本體意義上「停」。一台所謂「停機」的計算機，它的原子仍在熱運動，它仍在與環境交換能量，宇宙不會為任何計算暫停一拍。這裡需要一個關鍵澄清：計算並不是基板本身，而是我們強加在基板軌跡上的一個模式——一個從物理動力學到抽象狀態的解碼映射。當我們說一個計算「停了」，我們指的是這個映射抵達了一個不動點，或這個映射本身崩解（如硬體故障使解碼不再對應）。基板繼續運動，但運動的不再是「那個計算」，而是基板的其他動力學。

於是「之後它會動起來」這句直覺是對的，但需要被精確化：動起來的是載體，不是那個已經失去相干性的計算模式。一台藍屏的機器在熱力學上絲毫沒有靜止；它只是離開了我們的解碼映射還能對它說話的區域。停機，是模式的事；運動，是基板的事。兩者的混淆，是後文所有混亂的源頭，也是日常那句「就是壞了」之所以同時正確又貧乏的原因。

3. 第一次退場：有限基板把邏輯的牆換成時間的牆

任何真實計算機的記憶體是有限的。一台具有 b 位元狀態的確定性機器，其可能組態至多 2^b 個。這樣的機器不是圖靈機，而是一台有限狀態機。而有限狀態機的停機是可判定的：模擬至多 2^b 步，若仍未停機，則由鴿籠原理它必已重訪某一組態；確定性使其後續永遠週期重複，故永不停機（命題 A1）。

這似乎把停機問題「解消」了——對任何真實硬體，它會不會停，原則上可算。但這個結論是一個陷阱，因為「原則上」這三個字承載了 2^b 這個天文數字。對一台僅有數 GB 記憶體的機器，2^b 遠超過宇宙當前年齡內可執行的任何步數。於是真正發生的事不是不可判定性消失，而是它換了材質：邏輯上不可判定的牆，變成了一道時間上不可行的牆。判定程序存在，但執行它所需的時間本身就超出了任何基板的壽命。

這給出本文的第一條結構性洞見：想繞過停機問題的努力，最終總是在別處重新發現它。有限基板把它從可計算性的領域，推進到了複雜度與物理的領域。牆沒有被拆掉，只是換了建材——從「邏輯」做的，換成「時間」做的。

3.1 補充：硬體層與程式層的必要區分

上述論證處理的是硬體層：一台具有 b 位元固定狀態的機器作為有限狀態機，其停機技術上可判定。但這個論証容易遮蓋一個必須明確標清楚的區分：停機問題的不可判定性，根本來源不是圖靈機的無限紙帶，而是自我指涉與對角化論證——任何圖靈完備（Turing-complete）的計算模型都攜帶這個結構，與硬體是否有限無關。

圖靈機的無限紙帶是圖靈完備性在一個特定形式模型上的實現方式；「無限」是這個模型的技術規格，不是不可判定性的真正來源。對角化論證的力量在於自我指涉的可能性，而自我指涉在任何表達力足夠的計算模型中都存在——無論底層硬體是不是有限的。

當一個工程師問「這段程式會不會停機」，他問的對象是程式作為圖靈完備抽象物的行為。Python、C++、Haskell 等語言的程式設計模型在設計上是圖靈完備的，其程式的抽象語義定義在無界資源假設下。對這個抽象物的分析，不可判定性仍然完整存在；有限記憶體只是物理地截斷了程式的執行路徑，截斷不等於消解——對角化論證的結構仍在程式的抽象規格裡，只是沒有足夠的記憶體讓它完整展開。

因此「真實電腦是有限狀態機所以停機可判定」這個陳述，精確地說，成立的層次是：此特定硬體組態、以 b 位元固定狀態、在封閉條件下執行的物理過程，其完成與否可判定（代價是 2^b 步複雜度）。 它不成立的層次是：程式語言圖靈完備語義下，對程式抽象行為的靜態分析——這個問題的不可判定性結構不被有限硬體消除，只被物理地壓抑。

本文的「牆換材質」論點精確適用於物理執行層。程式分析層的牆是另一道牆，有限硬體沒有把它一起換掉；它只是讓不可判定的程式在記憶體耗盡前先死，而非讓分析這件事變得可行。這兩道牆在日常使用中被同一句「它壞了」掩蓋——但它們的理論地位並不相同。

4. 物理地基：存在，或消亡

第 3 節的論證仍停在資訊層。但有一條更物理的陳述在底下撐著它。

物理基板擁有有限的自由能。由 Landauer 原理，每一次不可逆的位元操作至少耗散 kT·ln2 的能量（室溫下約 3×10⁻²¹ 焦耳，此為說明性數量級）。因此一個基板能執行的不可逆操作次數，被其自由能上界 N ≤ E/(kT·ln2) 所限。再加上基板自身的有限壽命（元件衰變、退相干、電源耗盡），結論是：物理世界不存在「永遠運轉」這個選項。

於是 Turing 的二分——停，或永不停——在物理上塌成另一個二分：在基板死前完成，或基板先死。前者是計算抵達了被解碼為輸出的組態（存在/完成），後者是承載它的基板在抵達之前耗散或損壞（消亡）。這不再是一個可計算性陳述，而是一個有限時間、有限能量下的熱力學陳述。

必須誠實標註此處的界線：可逆計算在理想極限下能規避 Landauer 的逐步耗散，因此上述能量論證的嚴格形式只約束「不可逆」操作。但任何產生確定、可讀出、穩定輸出的計算，至少執行一次不可逆的讀出或重置，且任何真實裝置都是耗散的；更根本地，基板壽命有限這一點，獨立於可逆性爭議而成立。因此「沒有物理計算永遠運轉」這條結論，最穩固的地基不是 Landauer 單獨，而是「有限資源」這個更寬的事實——能量、時間、基板完整性三者皆有限——Landauer 只是其中可量化的一個下界範例。

5. 第二次退場：有限觀測窗把區分壓平

第 3、4 節從機器那側拿掉了無限。本節從觀察者那側拿掉它，而這才是日常那句「就是壞了」真正的來源。

任何真實觀察者——人、AI、或任何物理存在者——只在一個有限的觀測窗 W 內等待：一段耐心、一個截止期、一份預算、一段壽命。考慮一個黑箱觀察者，它只能看見計算的輸出通道。對任何真實停機時間超過 W 的程式（這包含了永不停機者），觀察者在 W 之前所能取得的證據——軌跡的有限前綴——在類型上完全相同：「到 W 為止未見停機」。

於是,從輸出通道單看,觀察者無法區分三件事:一個會在某個 t > W 才停的合法計算、一個永不停機的計算、一個已崩潰而不再產生可辨識輸出的死計算。三者映射到同一個判決:「W 內沒答案」≈「壞了」。那個在第 3 節還可判定的精細區分(慢 vs 循環),在有限窗下被進一步壓平成一個二值粗判。

這正是工程實務早已默認的事。每一個真實系統都有 timeout、watchdog、liveness probe——這些機制是工程界對「我從外面分不出來」的正式招供:既然分不出,那就設一個期限,到了就宣判失敗。觀察者面對的 operative 謂詞,從來不是 Turing 的「停不停」(Halts),而是「在我的期限內給不給答案」(HaltsBy)。而後者是平凡可判定的(命題 A4、A5)——代價是它一面倒地犧牲完整性換取可判定性:它會把那些 t = W+1 才停的計算,誤判為「壞了」。

6. 觀察者算力不變性:這篇的承重樑

至此可能有一個自然的反駁:更強的觀察者——更有耐心、更多算力、更未來的 AI——難道不能把這個壓平還原嗎?本節論證:幾乎不能,而它「不能」的方式,正是本文最該重壓的原創點。

考慮一族以窗 W(或算力預算)為索引的觀察者。隨 W 增大,HaltsBy(p, W) 對更多程式判得正確——任何在 t ≤ W 停的程式都被正確接住。但有三件事同時成立。其一,對每一個有限的 W,都存在程式(例如恰在 t = W+1 停者,或永不停者)使該觀察者判錯或判粗;沒有任何有限 W 能消去這一點,而「W 內答了 vs 沒答」這個判決結構,在每一個 W 都一模一樣——移動的只是門檻,不是結構。其二,具備分析能力(而非僅黑箱等待)的觀察者,能對可判定子類中的程式直接證明其終止性(如原始遞迴、具可證遞減度量者),從而縮小那個被迫丟進粗判的集合;這個可證終止集隨觀察者的邏輯強度增長(更強的形式系統證明更多終止性)。其三,然而一般的 Halts 謂詞,對每一個可計算觀察者仍不可判定(Turing,且對角論證可相對化):那個對抗性的不可判定核——自我指涉的對角程式——對任何可計算觀察者都不變。

合起來:觀察者算力能把期限往外推,能把可證終止的典型多數判得更細,卻動不了最壞情況的判決結構。換句話說,「停機問題的答案差異性不大」這個直覺,最成立的地方恰好是那個對所有觀察者都不變的最壞核;而它最不成立的地方(典型程式),正是可被更強觀察者逐步收編的部分。

此處必須標清楚承載這條不變性的關鍵假設:它要求所有觀察者都是物理可實現的——因而是有限的、可計算的(物理 Church–Turing 論題)。若准許某觀察者握有一個貨真價實的停機神諭,它當然能判定停機;但神諭是「無中生有的無界輸入」,沒有任何物理觀察者擁有它。本文的不變性,是在「沒有人坐得進無限座位」這個前提下的不變性。一旦你接受這個前提——而現實強迫你接受——則最未來的 AI 與今天的你,面對的是同一個「壞了」的桶,差別只在它的期限更遠。

7. 動力系統影子(詮釋層,非定理)

本節明確標為詮釋:以下是結構對應,不是已證的數學等價,刻意不宣稱證明。

把計算視為基板狀態空間上的一條動力系統軌跡,停機問題的詞彙會獲得一組動力學翻譯。停機,對應軌跡收斂到一個被解碼映射讀作「輸出」的不動點吸引子;非停機的週期行為,對應一個極限環;崩潰或故障,對應軌跡逃出原吸引域,或更劇烈地,向量場本身被改寫(硬體故障即相空間自身的形變)。

這個翻譯有真實的數學支撐而非純比喻:已知存在計算普適的動力系統,其長期行為不可判定——可將通用圖靈機嵌入光滑動力系統,使「軌跡長期落於何處」不可決定(此類結果見 Moore 1990 一脈)。這是停機問題在連續動力學中的影子:對足夠豐富的系統,長期行為無法比照著模擬更快地預測。

而這道「不模擬就測不準」的牆,與耦合振盪系統的同步崩潰、與混沌的敏感依賴,是同一道牆的不同切面。在耦合自適應控制的脈絡裡,過高的迴路增益會先把系統的異質結構連續壓平、再越過門檻翻入發散;可用的計算只活在中間那條窄帶——下界是耦合需足夠強才協調得起來,上界是增益一過門檻即失穩。停機(會不會落入輸出不動點)、同步崩潰(會不會被鎖進單一吸引子)、混沌不可預測(長期態能否被預測),於是顯現為同一個分岔結構被從三個方向命名。本文不主張它們在公理層等同,只主張它們共享「長期行為相對於有限觀察者不可預測」這一核心,且這種共享足以解釋為何同一套警告反覆出現在看似無關的領域。

8. 綜合與定位

本文的論點可一句收束:停機問題的咬合力,需要一台無界的機器與一個無限耐心的觀察者;物理從機器那側拿掉無限(有限基板→可判定但不可行,且熱力學上塌成完成或消亡),認識論從觀察者那側拿掉無限(有限窗→期限判決)。極限本身真實——定理對那個理想化無條件成立——但它既不可違反、也不可觀測,從任何有限座位看出去皆然,而所有物理座位都是有限的。因此「它壞了」不是無知的簡化,而是有限座位上唯一誠實的判決。

就學術定位而言,本文不宣稱發現新定理。其每一塊磚都立在既有工作上:有限狀態機停機的可判定性是教科書內容;物理計算的能量極限承自 Landauer、Bennett 與 Lloyd 一脈;動力系統中的不可判定性承自 Moore 等;不可判定性本身承自 Turing。本文的貢獻是綜合與重新framing:以「觀察者相對解消」作為組織性原則,把上述分散結果縫成「雙重隔開」這一個論點,並提出「觀察者算力不變性」(第 6 節)作為其中最值得獨立檢驗的命題。

9. 局限

本文的論證有數處需要審慎而非雄辯。第 4 節的熱力學二分依賴有限資源前提,其嚴格能量形式僅約束不可逆操作。第 6 節的不變性依賴物理 Church–Turing 論題;若該論題在某種新物理基板下失效(精確實數類比、特殊時空結構),則「未來不知道」這句保留是認真的,而非修辭。第 7 節是詮釋層,不應被讀成已證同構;把結構對應誇大為數學等價,是本文作者刻意避開的陷阱。這些不是論證的補丁,而是論點的真實邊界——一篇主張「極限活在無限裡」的論文,理應對自己論點的有限性同樣誠實。

10. 結語

Turing 在 1936 年描述的不是一台機器,是無限。停機問題之所以不可解,是因為它問的是「一個永遠跑得下去的東西會不會停」——而「永遠」本身就不在物理世界的詞彙表裡。把無限拿掉,神諭、超計算、不可判定性會一起退場,剩下的只有時間、能量,和「在耗盡之前算不算得完」。現實沒有停機問題;現實只有期限。而站在任何有限的座位上,我們連那期限底下的成因都看不見——只說得出一句:它停了。理論在無限遠處保留它的莊嚴,我們在這裡,各自看著自己的鐘。

附錄:半形式化命題與證明草圖

狀態聲明:本附錄為「合理性推導」(plausibility derivation),目的在檢驗主張是否可能成立,並非形式化證明。每條命題附其假設與一個狀態標籤——【定理】(已知標準結果)、【觀察】(由定義直接得出的非深刻陳述)、【詮釋】(結構對應,非數學等價)。讀者應將其視為論證骨架,而非定稿的形式系統。

命題 A1（有限基板停機可判定性）【定理】 設 M 為確定性機器,其總狀態(含記憶體)以 b 位元編碼,則 M 的組態空間大小 ≤ 2^b,且「M 在輸入 x 上是否停機」可判定。 假設:M 確定性、封閉(無外部輸入流注入、無真隨機源)。 草圖:模擬 M 至多 2^b 步。若停機,回報「停」。若執行滿 2^b 步仍未停,則由鴿籠原理,期間必有某組態 c 重複出現;由確定性,自首次重複起軌跡嚴格週期,故永不停,回報「不停」。∎(標準)

層次說明：本命題的「可判定」結論適用於封閉有限狀態機作為物理對象。對於在此硬體上執行的程式，若該程式以圖靈完備語言書寫，其作為抽象對象的停機性質——即「若給予無界資源，此演算法是否終止？」——仍然不可判定，獨立於硬體有限性而成立。命題 A1 不消解程式層的不可判定性；它只指出物理執行層的有限性使 2^b 步模擬在原則上可行，兩個層次的問題是不同的問題。

命題 A2（牆的換材,而非消失）【觀察】 A1 的判定程序最壞需 Θ(2^b) 步,對現實 b 超出任何物理可實現步數預算。故有限基板停機「可判定而不可行」:無界模型的不可判定性被複雜度層的不可行性取代,而非移除。 草圖:直接由 A1 的步數上界與物理步數預算(受第 4 節能量界限制)之比較得出。此為定性觀察,非定理。∎

命題 A3（熱力學二分:完成或消亡）【定理(條件式)】 設物理基板自由能為 E,溫度 T。則其可執行的不可逆位元操作數 N ≤ E/(kT·ln2)。結合基板有限壽命,任一物理計算必落入二者之一:(i) 在資源耗盡前抵達被解碼為輸出的組態(完成);(ii) 基板在抵達前耗散或失效(消亡)。不存在物理可實現的第三選項「永遠運轉」。 假設:Landauer 下界成立;計算含至少一次不可逆讀出;基板壽命有限。 草圖:由 Landauer,不可逆操作數受 E/(kT·ln2) 上界;有限壽命另給時間上界;二者皆有限,故計算步數有限,必在有限步內或抵達輸出態或基板離開運作區。可逆計算可規避逐步耗散界,但無法規避有限壽命界,故結論在「有限資源」前提下仍立。∎(條件式)

命題 A4（黑箱觀測壓平）【觀察】 設黑箱觀察者僅可見輸出通道,觀測窗為 W 步。對任意真停機時間 > W 的程式,觀察者於 W 內取得的證據類型恒為「W 內未見輸出」。故觀察者無法由輸出通道區分:(i) 將於 t > W 停的合法計算、(ii) 永不停計算、(iii) 已死計算。三者同判為「W 內無答案」。 假設:觀察者僅有輸出通道(無內部狀態自省、無源碼分析)。 草圖:三類程式於 [0, W] 的輸出通道投影相同(皆為「無輸出事件」),而判決僅為該投影之函數,故三類同判。∎

命題 A5（期限化即可判定粗化）【定理】 謂詞 HaltsBy(p, W)≜「p 是否於 W 步內停機」可判定(界限模擬 W 步即得)。它是 Halts(p) 的單側逼近:無偽陽性,有偽陰性(凡 t > W 才停者被判「否」)。 草圖:界限模擬必於 W 步內終止並給出明確判答,故可判定。其錯誤僅來自 t > W 之程式被歸入「否」,即單側。∎(標準)

命題 A6（觀察者算力近不變性)【混合:部分定理,部分觀察】 考慮以窗 W(或算力)索引的觀察者族。則: (a)【觀察】對每一有限 W,存在程式使 HaltsBy(·, W) 判錯或判粗;判決結構「W 內答 vs 不答」在所有 W 同構,僅門檻移動。 (b)【定理】具分析能力的觀察者可對可判定子類(如具可證遞減度量者)證明終止;此可證終止集隨觀察者邏輯強度單調增長。 (c)【定理】一般 Halts 對任一可計算觀察者不可判定(Turing;對角論證相對化)。 故:算力移動期限、收編典型多數,但最壞核之判決結構不變。 關鍵假設:所有觀察者物理可實現,因而可計算(物理 Church–Turing)。若准許貨真價實的停機神諭,(c) 失效——但無物理觀察者擁有神諭。 草圖:(a) 取 p 恰於 t = W+1 停即得反例;判決僅二值,結構平凡同構。(b) 可證終止集 = 該觀察者形式系統可證 p 終止之 p 集,隨系統證明力增大(經典結果,關聯證明論序數)。(c) 對角程式 d:「若停機判定器對 d 回報停則發散,否則停」,對任一可計算判定器導出矛盾;此論證對相對化於任一可計算 oracle 仍成立。∎

命題 A7（動力系統對應)【詮釋,非定理】 將計算視為狀態空間上的動力軌跡,則:停機 ↔ 收斂至被解碼為輸出之不動點吸引子;非停機週期 ↔ 極限環;崩潰 ↔ 逃出吸引域或向量場形變。對計算普適之動力系統,長期吸引子之判定不可決(嵌入通用 TM;Moore 1990 一脈)。 狀態:本命題為結構對應,非主張公理層數學等同。其可辯護的硬核僅為:存在動力系統,其長期行為不可判定,且此不可判定性與停機問題經由 TM 嵌入相連。吸引子分類(停=不動點、循環=極限環)為解釋性映射,提供直覺而不承擔證明義務。 與耦合/同步之關係【詮釋】:三者共享「長期行為相對於有限觀察者不可預測」之核心;不主張等同,僅主張此共享解釋了同一套穩定性警告為何跨域重現。∎

本文件為概念論文草稿。本體論證屬計算哲學/理論 CS 之綜合與重新framing;附錄為合理性推導,非形式化證明。所有具體數值(如 kT·ln2 之數量級)為說明性,推導依賴之前提已於正文第 9 節與各命題假設處標明。