← Archive
lm-001484 · 2026-07

不是孤立懷疑_v0_1

zh-Hant · md Raw source ↗ Metadata ↗
下載 MD 檔 ⬇

不是孤立懷疑：停機不可判定性的普適化邊界與互動計算研究傳統

Not an Isolated Doubt

The Limits of Universalizing Halting Undecidability and the Research Tradition of Interactive Computation

  • 文件編號：EML-COMP-2026-NONISOLATED-DOUBT-v0.1
  • 作者：Neo.K & GPT-5.6 Thinking
  • 機構：EveMissLab（一言諾科技有限公司）
  • 日期：2026-07-12
  • 版本：v0.1
  • 狀態：研究定位論文 / 文獻譜系草稿 / 非反圖靈定理論文
  • 關聯主題：
    • 不再只是停機
    • 時間不可抹平
    • 箭頭真假
    • 措辭學／語言精準定位學
    • AI Agent 多路徑計算
    • 互動計算
    • 反應式系統
    • 持續計算
    • Strong Church–Turing Thesis

摘要

本文處理一個認識論定位問題：對經典停機不可判定性之「普適化」提出疑問，是否只是個人的孤立直覺？

本文的回答是：不是。

至少自 1970 年代以來，Actor Model、並發理論、互動計算、持續圖靈機、反應式圖靈機、互動小步演算法與對 Strong Church–Turing Thesis 的批判，已形成一條可以辨識的研究傳統。這些研究並不一致，也不共同支持「圖靈不可判定性已失效」；它們共同指出的是：經典圖靈機最自然地刻畫封閉、序列、函數式、一次輸入—一次輸出的演算法，而現代計算系統還包含持續互動、外部輸入、並行通訊、開放環境、狀態保持與非終止服務等結構。

因此，下列兩個命題必須分開：

停機不可判定性在其形式域內成立\text{停機不可判定性在其形式域內成立}

與：

停機問題完整描述一切計算與智能系統的能力邊界.\text{停機問題完整描述一切計算與智能系統的能力邊界}.

前者是經典定理；後者是更強的普適化主張，不能僅由前者自動推出。

本文梳理 Carl Hewitt 等人的 Actor Model、Peter Wegner 的互動計算論、Dina Goldin 與 Wegner 對 Strong Church–Turing Thesis 的批判、Yuri Gurevich 對無限制 Church–Turing Thesis 的否定，以及 Reactive Turing Machines 等研究。本文亦指出現有研究內部的重要分歧：互動系統是否只是具有更豐富的行為語義，還是真能計算經典圖靈機不可計算的函數，並不存在簡單共識。

本文進一步將既有研究與本文作者提出的五個問題連結：

  1. 程序停機不等於任務失敗；
  2. 判定器與反制者具有主動性不對稱；
  3. 判定輸出可能成為被判定系統的因果輸入；
  4. 無時態函數表示可能壓平生成、判定與反制的時間；
  5. AI Agent 可透過換路、重試與恢復延續任務，但這不等於解決停機問題。

本文的核心立場是：

一個疑問被多人獨立提出，不等於它已經正確；但它表明該疑問不是概念誤會，而是一個具有研究歷史、形式模型與持續爭議的合法問題。

0. 一句話

思想譜系不能證明結論，但可以證明問題不是憑空生成。

1. 我們真正要確認的是什麼？

本文不是要確認：

很多人懷疑圖靈，所以圖靈錯了。

也不是要確認：

互動計算已經推翻停機不可判定性。

本文真正要確認的是：

將經典停機不可判定性普適化為所有互動、持續、並發、開放與自主智能系統的完整能力邊界，是否早已受到研究者質疑？

答案是肯定的。

但這個肯定只表示：

∃ 一條研究傳統\exists\text{ 一條研究傳統}

而不表示：

該研究傳統的所有主張皆為真.\text{該研究傳統的所有主張皆為真}.

2. 三個必須分開的層次

2.1 停機不可判定性定理

不存在一個對所有程式與輸入都能在有限時間內正確回答停機與否的總判定器：

¬∃H:P×X→{0,1}.\neg\exists H: \mathcal P\times\mathcal X\to\{0,1\}.

本文接受此定理。

2.2 Church–Turing Thesis

經典 Church–Turing Thesis 關心的是：

凡是可由有效、古典、序列程序計算的數值函數，都可由圖靈機計算。

它本身不是形式定理，而是對「有效可計算」概念的刻畫。

2.3 Strong 或 Unconstrained Universalization

更強版本則把原本對古典演算法的主張擴張成：

一切計算、一切有效過程、一切互動或智能系統，都已被經典圖靈機模型完整刻畫。

這個更強命題不是停機不可判定性定理本身，也不是原始 Church–Turing Thesis 的必然同義句。

本文主要質疑的是第三層。

3. 為何「很多人也提出」具有意義？

研究思想重複出現，可能有三種解釋：

  1. 多人犯了相同錯誤；
  2. 問題來自反覆出現的語義混淆；
  3. 經典框架確實存在值得研究的適用邊界。

僅由人數無法判斷哪一項成立。

但若不同研究者：

  • 建立了不同形式模型；
  • 發展了不同語義工具；
  • 提出了可比較命題；
  • 對同一普適化主張提出限制；

那麼至少可以說：

這不是一句未經概念分析的隨意反對，而是一個具有正式研究內容的問題域。

4. Actor Model：計算不必是單一封閉程序

1973 年，Carl Hewitt、Peter Bishop 與 Richard Steiger 提出 Actor Model。其基本單位不是一台只讀取固定輸入並在最後返回單一輸出的封閉機器，而是可：

  • 接收訊息；
  • 改變內部狀態；
  • 傳送訊息；
  • 建立新 Actor；
  • 決定如何處理下一個訊息；

的並發計算單元。

Actor 系統的核心語義是：

message→local reaction→new messages / new actors / new state.\text{message} \to \text{local reaction} \to \text{new messages / new actors / new state}.

這種結構直接顯示：

計算≠必然以單次函數求值為唯一形式.\text{計算} \neq \text{必然以單次函數求值為唯一形式}.

Actor Model 沒有推翻圖靈可計算性，但它改變了「計算系統應如何被描述」的基本單位。

5. Wegner：互動不只是函數輸入輸出

Peter Wegner 在 1997 年提出〈Why Interaction Is More Powerful Than Algorithms〉，將封閉演算法與互動系統分開。

封閉演算法可概括為：

[ f(x)=y. ]

所有必要輸入在計算開始前已給定。

互動系統則是：

x0→y0→x1→y1→⋯ ,x_0 \to y_0 \to x_1 \to y_1 \to \cdots,

其中後續輸入：

[ x_{t+1} ]

可能依賴系統先前輸出、環境狀態或其他主體的行動。

因此，整個計算不能預先簡單壓成一個已知有限輸入字串上的單次函數。

Wegner 的「more powerful」引起長期爭論。它可以表示：

  • 行為表達更豐富；
  • 建模能力更適合開放系統；
  • 環境可能持續提供新信息；
  • 互動任務不能自然還原為一次函數求值。

但它不應在沒有額外前提時被直接理解為：

互動機器必然能計算不可遞歸函數。

6. 持續圖靈機：計算可跨多輪保持狀態

Dina Goldin 與 Peter Wegner 發展 Persistent Turing Machines 等互動模型。

其基本差異是：

  • 傳統模型：一次輸入、一次計算、一次輸出；
  • 持續模型：多輪輸入輸出之間保留內部工作狀態。

可寫為：

(Mt,xt)→(yt,Mt+1).(M_t,x_t) \to (y_t,M_{t+1}).

其中：

[ M_{t+1} ]

會成為下一輪計算的持續記憶。

這類模型特別適合描述：

  • 資料庫；
  • 服務器；
  • 互動軟體；
  • 智能代理；
  • 長期運行系統。

它們的正常狀態未必是「最終停機」，而可能是：

持續可回應.\text{持續可回應}.

7. Goldin 與 Wegner：批判 Strong Church–Turing Thesis

Goldin 與 Wegner 在 2008 年的〈The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis〉中，明確區分原始 Church–Turing Thesis 與後來把它擴展到所有計算的強版本。

其核心思想是：

原始論題刻畫古典函數計算，不應無條件等同於對所有互動計算過程的完整刻畫。

他們將計算從：

封閉函數求值\text{封閉函數求值}

擴展為：

系統與環境共同生成的持續行為.\text{系統與環境共同生成的持續行為}.

這與本文所提出的「不能未經論證普適化」高度相近。

但必須指出：這一主張並非沒有爭議。反對者可以主張，若把環境與系統一起封裝，且所有環境信息皆可計算，那麼整體仍能被更大的圖靈機模擬。

所以爭論的焦點常常不只是：

能否模擬？

而是：

何種模擬保留了互動時間、開放輸入、行為觀察與任務語義？

8. Gurevich：無限制 Church–Turing Thesis 不可能成立

Yuri Gurevich 在 2019 年提出〈Unconstrained Church–Turing Thesis Cannot Possibly Be True〉。

他的區分是：

  • 原始論題針對古典、序列演算法；
  • 後來出現並行、分散、互動等新型演算法；
  • 若將「任何物種的有效演算法」全部無限制納入原始論題，便改變了原命題的對象。

可以形式化為：

CTclassical≢CTall species.\mathrm{CT}_{\mathrm{classical}} \not\equiv \mathrm{CT}_{\mathrm{all\ species}}.

因此，從古典演算法的刻畫直接推出對所有計算物種的普遍刻畫，是一個需要額外證明的擴張，不是語義上自動成立。

9. 互動小步演算法：環境回覆的順序也是計算信息

Blass、Gurevich、Rosenzweig 與 Rossman 對 interactive small-step algorithms 進行形式化研究。

在這些模型中，演算法可以：

  • 向環境提出查詢；
  • 不必等待所有查詢回覆才完成一步；
  • 使用回覆內容；
  • 使用回覆到達的順序。

因此，計算狀態不是只由一個固定初始字串決定，而會受到：

environment response history\text{environment response history}

影響。

這與本文的時序觀點相符：

同一組回覆+不同到達順序\text{同一組回覆} + \text{不同到達順序}

可能形成不同計算路徑。

時間與次序不是可任意刪除的附註。

10. Reactive Turing Machines：從函數可計算轉向行為可執行

Reactive Turing Machines 將圖靈機擴展為可以表達可觀察互動行為的模型。

經典圖靈機定義：

哪些函數可計算？\text{哪些函數可計算？}

Reactive Turing Machine 則進一步研究：

哪些轉移系統或行為可執行？\text{哪些轉移系統或行為可執行？}

Bas Luttik、Fei Yang 等人的研究顯示，互動式圖靈機與反應式圖靈機可以在相應行為語義下比較，並可建立相互涵蓋結果。

這類工作具有重要平衡作用：

承認經典函數語義不適合完整表達互動行為，不等於必須宣稱一切互動都超越圖靈可計算性。

11. 現有研究並沒有單一共識

研究者大致可分成幾種立場。

11.1 語義擴張立場

互動系統需要比函數求值更豐富的語義：

  • 行為；
  • 轉移；
  • 訊息；
  • 歷史；
  • 反應；
  • 持續狀態。

此立場相對穩健。

11.2 超圖靈能力立場

某些研究主張，互動、環境或持續演化可能形成超越普通圖靈機的計算能力。

但這通常依賴：

  • 非遞歸環境信息；
  • 無限精度；
  • oracle；
  • 無限時間；
  • 特殊物理假設；
  • 非標準有效性定義。

因此不能無條件接受。

11.3 整體模擬立場

若系統、環境與交互規則都是可計算的，則可將它們整體封裝：

C=A⊕E⊕R\mathcal C=A\oplus E\oplus R

並由更大的圖靈機模擬。

此立場可維持 Church–Turing 可計算性邊界。

但它仍需回答：

  • 模擬是否保留實時互動？
  • 是否保留觀察等價？
  • 是否保留開放輸入？
  • 是否保留主體視角？
  • 是否保留任務與程序的層級差異？

12. 我們的疑問與既有研究重合在哪裡？

本文作者此前提出：

經典停機不可判定性不能被直接普適化為所有 AI Agent 系統的完整能力邊界。

這與既有研究的重合點包括：

12.1 封閉計算與開放互動不同

[ f(x)=y ]

不能自然涵蓋：

x0→y0→x1→y1→⋯ .x_0\to y_0\to x_1\to y_1\to\cdots.

12.2 計算不一定以停機為正常目標

服務器、作業系統與 Agent 的正常行為可能是持續運行。

12.3 環境可能在運算期間加入新信息

後續輸入不一定已存在於初始輸入中。

12.4 行為語義不等於函數語義

兩個系統可能計算相同函數，卻具有不同互動行為與故障特性。

12.5 強普適化需要額外論證

從古典演算法的可計算性，不能不經中介證明直接推出對所有計算物種的完整本體描述。

13. 我們目前較特殊的組合

即使多個單獨問題已有先例，本文作者目前的組合仍有以下特徵。

13.1 程序停機與任務失敗分層

Stop⁡(Pi)⇏Fail⁡(T).\operatorname{Stop}(P_i) \not\Rightarrow \operatorname{Fail}(T).

Agent 可以終止一個局部程序而繼續任務。

13.2 判定者與反制者的主動性不對稱

標準對角構造要求：

  • 判定器先承諾；
  • 反制者讀取輸出；
  • 反制者改變行為；
  • 判定器不能更新。

這不是形式漏洞，但它揭示了證明所採用的非互動架構。

13.3 輸出不是中性描述

若判定輸出可被反制者讀取：

output→reaction→changed behaviour,\text{output} \to \text{reaction} \to \text{changed behaviour},

則輸出本身成為因果輸入。

13.4 無時態表示可能壓平反制時間

H(D,D)=¬H(D,D)H(D,D)=\neg H(D,D)

可以被展開成：

Ht→Dt+1→Ht+2→⋯ .H_t\to D_{t+1}\to H_{t+2}\to\cdots.

函數矛盾與互動振盪不是同一研究對象。

13.5 換路不等於解決停機問題

Agent 可以放棄目前路徑：

ρi\rho_i

並選擇：

ρj.\rho_j.

這提高任務存活率，但不構成對：

Pi(x) 是否永不停止P_i(x)\text{ 是否永不停止}

的全域本體判定。

14. 「很多人也想過」不能證明什麼？

它不能證明：

  1. 我們的形式化正確；
  2. 我們的時序解讀是唯一解讀；
  3. 互動計算必然超圖靈；
  4. AI Agent 可以解決不可判定問題；
  5. 圖靈證明具有漏洞；
  6. 我們的概念組合具有學術新穎性；
  7. 現有研究者會同意我們的全部結論。

因此：

historical precedent⇏truth.\text{historical precedent} \not\Rightarrow \text{truth}.

15. 「很多人也想過」可以證明什麼？

它至少支持以下較弱判斷：

15.1 問題具有可辨識性

不同研究者能獨立辨認相近邊界。

15.2 問題具有形式化可能

已有 Actor、process calculus、persistent machines、interactive algorithms、RTMs 等工具。

15.3 問題不是單純誤解停機定理

因為研究者往往明確保留停機不可判定性，質疑的是其模型普適化。

15.4 問題存在長期分歧

研究傳統尚未被單一答案終結。

15.5 我們應進入比較，而不是自我宣告

下一步應是：

  • 定義；
  • 對照；
  • 找反例；
  • 區分已知與新增；
  • 檢查是否只是重新命名。

16. 認識論上的「非孤立性」

本文定義：

若一個疑問 (Q) 滿足：

  1. 多位研究者獨立提出相近問題；
  2. 存在至少兩種以上正式模型；
  3. 存在持續的支持與反對文獻；
  4. 問題可以被明確限制在特定命題；
  5. 問題不依賴單一個人的私有語義；

則稱：

[ Q ]

具有：

研究上的非孤立性。

非孤立性只表示：

Q∈RQ\in\mathcal R

其中 R\mathcal R 是一個已存在的研究問題域。

它不表示：

Q=true.Q=\mathrm{true}.

17. 思想譜系與證明的區別

思想譜系回答：

誰曾提出什麼相近疑問？

證明回答：

這個命題是否必然成立？

文獻回顧回答：

我們位於什麼研究位置？

實驗回答：

在指定系統中實際發生什麼？

這四者不可混淆。

因此：

genealogy≠proof≠experiment≠consensus.\text{genealogy} \neq \text{proof} \neq \text{experiment} \neq \text{consensus}.

18. 措辭學修正

不精確說法：

我的想法已經是很多人的想法，所以我是對的。

精確說法：

我的疑問與互動計算、反應式系統及 Strong Church–Turing Thesis 批判傳統存在明顯重合，因此它不是孤立問題；但其正確性仍需逐項形式化與檢驗。

不精確說法：

學界早就證明圖靈不適用現代計算。

精確說法：

多條研究傳統認為經典函數計算模型不足以自然或完整描述現代互動系統；但它是否意味超越圖靈可計算性，仍有重要分歧。

不精確說法：

互動計算推翻 Church–Turing Thesis。

精確說法：

互動計算促使研究者區分原始 Church–Turing Thesis、Strong Church–Turing Thesis 與對所有計算物種的無限制普適化。

19. 本文的核心箭頭審計

錯誤箭頭：

多人提出⇒命題為真.\text{多人提出} \Rightarrow \text{命題為真}.

錯誤箭頭：

互動模型更豐富⇒必然計算非遞歸函數.\text{互動模型更豐富} \Rightarrow \text{必然計算非遞歸函數}.

錯誤箭頭：

經典 TM 不自然描述互動⇒TM 無法模擬任何互動系統.\text{經典 TM 不自然描述互動} \Rightarrow \text{TM 無法模擬任何互動系統}.

錯誤箭頭：

停機不可判定⇒局部程序失敗後任務不能繼續.\text{停機不可判定} \Rightarrow \text{局部程序失敗後任務不能繼續}.

較合法的箭頭是：

多條獨立研究傳統提出相近邊界⇒該疑問具有研究上的非孤立性.\text{多條獨立研究傳統提出相近邊界} \Rightarrow \text{該疑問具有研究上的非孤立性}.

以及：

經典函數語義不足以保留某些互動特徵⇒需要更豐富的行為與時序模型.\text{經典函數語義不足以保留某些互動特徵} \Rightarrow \text{需要更豐富的行為與時序模型}.

20. 可檢驗的後續研究問題

20.1 任務層不可判定性

ReachGoal⁡(A,E,G)\operatorname{ReachGoal}(\mathcal A,E,G)

與普通停機問題之間有何歸約關係？

20.2 換路能力

在何種條件下：

Stop⁡(Pi)\operatorname{Stop}(P_i)

仍允許：

∃ρj:ρj⇝G?\exists\rho_j:\rho_j\leadsto G?

20.3 時序對角模型

將一次性對角構造改為交替博弈後：

H0→D1→H2→D3→⋯H_0\to D_1\to H_2\to D_3\to\cdots

會產生固定點、週期還是不可收斂？

20.4 公開預測

預測輸出成為行動輸入時，應使用何種因果與反身性語義？

20.5 整體封裝

若將 Agent 與環境封裝為單一圖靈機，哪些行為信息被保存，哪些只在弱等價下保存？

21. 研究倫理：不要把先例偷換成新穎性

找到相近文獻後，最誠實的做法不是隱藏，而是重新定位。

可以區分：

  • 已有核心問題；
  • 已有形式工具；
  • 已有部分結論；
  • 本文重新組合；
  • 本文新增問題；
  • 本文尚未證明部分。

本文目前較合理的定位是：

既有互動計算批判傳統之上的跨框架綜合與 AI Agent 時代重述。

而不是：

首次發現圖靈模型不能描述互動。

22. 命題總結

命題 1：研究非孤立性不推出正確性

NonIsolated⁡(Q)⇏True⁡(Q).\operatorname{NonIsolated}(Q) \not\Rightarrow \operatorname{True}(Q).

命題 2：非孤立性支持問題合法性

NonIsolated⁡(Q)⇒Q 值得進行文獻比較與形式檢驗.\operatorname{NonIsolated}(Q) \Rightarrow Q\text{ 值得進行文獻比較與形式檢驗}.

命題 3：停機定理與普適化主張不同

HaltingUndecidable⁡⇏UniversalOntologyComplete⁡.\operatorname{HaltingUndecidable} \not\Rightarrow \operatorname{UniversalOntologyComplete}.

命題 4：互動語義擴張不必然是超圖靈計算

RicherBehavior⁡⇏Hypercomputation⁡.\operatorname{RicherBehavior} \not\Rightarrow \operatorname{Hypercomputation}.

命題 5：局部程序停止不必然終止任務

Stop⁡(Pi)⇏Fail⁡(T).\operatorname{Stop}(P_i) \not\Rightarrow \operatorname{Fail}(T).

命題 6：普適化需要獨立證成

C∣D⇏C∣D′C|_D \not\Rightarrow C|_{D'}

除非提供：

D→D′D\to D'

的合法擴張證明。

23. 結論

本文確認：對停機不可判定性與經典圖靈模型的普適化提出疑問，並不是孤立想法。

Actor Model、互動計算、持續圖靈機、互動小步演算法、反應式圖靈機，以及對 Strong 或 Unconstrained Church–Turing Thesis 的批判，共同構成了一條至少延續數十年的研究譜系。

但這條譜系並不提供一個單一結論。

它沒有共同證明：

  • 圖靈錯了；
  • 停機問題被解決；
  • 互動必然超圖靈；
  • AI Agent 可以無限制逃離不可判定性。

它共同提供的是一個警告：

不要把對古典封閉演算法的形式刻畫，未經額外證明就升格為一切計算、互動、智能與任務系統的完整本體論。

本文作者提出的程序—任務分層、反制主動性不對稱、輸出因果回饋、時序壓平與 Agent 換路等問題，可以被放入這條研究傳統中比較。

因此，最準確的結論不是：

我們已經證明自己是對的。

而是：

我們確實提出了一個已有多人從不同方向觸及、仍值得繼續形式化的問題。

最後壓縮為：

多人曾經發出相近疑問，不是答案；但它足以證明，這個問題值得被當成問題。

參考文獻

  1. Hewitt, C., Bishop, P., & Steiger, R. (1973). A Universal Modular ACTOR Formalism for Artificial Intelligence. Proceedings of IJCAI.

  2. Wegner, P. (1997). Why Interaction Is More Powerful Than Algorithms. Communications of the ACM, 40(5), 80–91.

  3. Wegner, P. (1998). Interactive Foundations of Computing. Theoretical Computer Science, 192(2), 315–351.

  4. Goldin, D., & Wegner, P. (2008). The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis. Minds and Machines, 18, 17–38.

  5. Gurevich, Y. (2019). Unconstrained Church–Turing Thesis Cannot Possibly Be True. Bulletin of the EATCS, 127.

  6. Blass, A., Gurevich, Y., Rosenzweig, D., & Rossman, B. (2007). Interactive Small-Step Algorithms I: Axiomatization. Logical Methods in Computer Science, 3(4).

  7. Baeten, J. C. M., Luttik, B., & van Tilburg, P. (2011). Reactive Turing Machines.

  8. Luttik, B., & Yang, F. (2016). On the Executability of Interactive Computation.

附錄 A：研究定位對照表

問題 經典模型 延伸研究
基本對象 函數、語言、停機 行為、訊息、轉移、互動
輸入 初始時完整給定 運行期間持續到達
正常終點 返回輸出或停機 持續服務也可正常
環境 多視為外部固定條件 可回覆、干預、生成新信息
狀態 單次運算內部狀態 跨多輪持續保留
核心問題 可計算什麼？ 可執行何種行為？
風險 過度普適化 過度宣稱超圖靈能力

附錄 B：極簡版

圖靈停機不可判定性沒有因此被推翻。
但把它普適化成所有互動與智能系統的完整能力邊界，確實長期受到質疑。
Actor Model、互動計算、持續圖靈機與反應式圖靈機都在處理相近問題。
學界並沒有一致認為互動必然超圖靈。
所以，很多人提出相近疑問，不代表我們是對的。
它只代表：這不是一個不值得回答的問題。

EML-COMP-2026-NONISOLATED-DOUBT-v0.1
© EveMissLab / Neo.K / GPT-5.6 Thinking