如何證明不存在一種演算法，對任何一個程序及相應的輸入數據，都可以判斷是否會出現死循環？

01-04

https://en.m.wikipedia.org/wiki/Halting_problem

通用的不存在， @陳碩的鏈接裡面就是，另外從這個可以得到很多「神奇」演算法也不存在比如判斷外延相等性……

不過另一方面，保守地判斷某個程序（或者 Lambda 項）必然終止的演算法還是有不少的。對此類演算法它們可以得出以下兩者結論之一：

此程序必然終止
此程序可能有死循環 / 無限遞歸

一個經典的例子就是 Foetus 終止分析，它會檢查所有遞歸調用看是否每次遞歸的數據結構都比原來更小。

既然 @Lyken 說到離散數學，那麼我來介紹一下K. H. Rosen在其著作《離散數學及其應用》中第2章第5節，講解集合的基數時設置的一系列習題：

預備部分先證明一些集合上的定理

15. Show that if A and B are sets, A is uncountable, and A ? B, then B is uncountable.

包含不可數集合的集合亦不可數。

16. Show that a subset of a countable set is also countable.

可數集的子集亦可數。

?27. Show that the union of a countable number of countable sets is countable.

可數多個可數集的並是可數的。

從這裡就要正式開始了，先是程序

?29. Show that the set of all finite bit strings is countable.

所有的有限長01串的集合是可數的。
（用到27）

?37. Show that the set of all computer programs in a particular programming language is countable. [Hint: A computer program written in a programming language can be thought of as a string of symbols from a finite alphabet.]

某一個程序語言的所有程序是可數的。[每個程序被視為有限字母表上的一個符號串]
（注意這裡不是雙射，並不是每個串都反過來直接就是程序[你瞎寫一堆ascii符號，g++讓你過編譯嗎？]用到16）

然後是函數

?38. Show that the set of functions from the positive integers to the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is uncountable.[Hint: First set up a one-to-one correspondence between the set of real numbers between 0 and 1 and a subset of these functions. Do this by associating to the real number 0.d1d2 . . . dn . . . the function f with f(n) = dn.]

從正整數映射到{0~9}的函數的集合不可數。[通過用0.d1d2...dn的方式將每個函數映射到一個0,1的實數]
（(0,1)的實數可以通過康托對角化證明不可數是已知的）
（注意，兩個串可能是同一實數，比如0.100...和0.099...，所以要為每個實數找到一個函數，進而得出所有這樣函數的集合不可數，用到15）

最後是真正的重頭戲

?39. We say that a function is computable if there is a computer program that finds the values of this function. Use Exercises 37 and 38 to show that there are functions that are not computable.

一個函數是可計算函數即存在一個程序能求出它的值，存在不可計算的函數。
（這裡才是真正的用到集合不等勢，用到37和38&最後這句似乎已經不需要了&）

有了這套題目，再加上一些輔助的動作（程序能算就算，不能算就死循環），就可以得到題主的疑問了

———————————————————————————————————————————

如果和Lyken的答案對比一下，可以發現幾個關鍵的差異

很多映射其實都不是雙射（雖然很大程度上可能只是為了說起來簡單）
對角化的對象的是函數，而不是程序

如果去掉這兩個差異點，嚴謹程度其實是有一定程度損傷的。

（我個人覺得，講到康托對角化的時候，有一個思考題是必做的：「為什麼對角化方法不會推出整數集不可數？」）

———————————————————————————————————————————

儘管如此，Rosen的這套題目，仍然只是給剛剛學習了離散數學的初學者一個比較直觀的認識，並不能說是非常、非常嚴格的一套證明。（比如，程序和遞歸函數之間的關係並沒有被很好的建立起來，甚至沒有很好的定義什麼是程序，形式化的程度不夠）而且，如果是對數理邏輯有一定了解的話，也可以看出這樣一套下來證明的其實比圖靈的停機證明/哥德爾的不完全性定理約束要強，並不能作為一個替代。

———————————————————————————————————————————

順便安利一下，Rosen這書非常棒的，內容之豐富、措辭之嚴謹在上面的題目中已經有一點體現了，然而此書最寶貴之處，在於每隔幾頁就會出現在下邊欄的人xiao物gu傳shi記，既可以讓你在學習中稍微放鬆一下（或者翻開書假裝學習），還可以增長見聞（在歷史人物上找一找被碾壓的感覺），一箭雙鵰。

———————————————————————————————————————————

最後還是要說一句，你乎編輯器這麼難用，還不如支持一下Markdown，我感覺裸寫HTML我都會寫的更舒服一點。

複製粘貼一下停機問題的證明吧

假裝存在一個函數名叫halt_judge()可以判斷輸入的代碼是否會死循環，假如返回true則代碼會死循環。

然後構造一個新的函數fuck_your_mother()

void fuck_your_mother(void) { if (halt_judge(ST)) return ; while (true) { printf("fuck your mother! "); } return ; }

如果ST所代表的代碼會死循環，那麼fuck_your_mother會直接退出，如果ST代碼不會死循環，那麼fuck_your_mother會不斷地列印fuck your mother!

那麼，如果輸入的ST就是函數fuck_your_mother呢？

這不就是著名的停機問題嗎，關於這個問題有個漂亮的證明方法，是圖靈給出的。

停機問題、Chaitin常數與萬能證明方法

康托爾、哥德爾、圖靈——永恆的金色對角線(rev#2)

這個問題等價圖靈停機問題

類比於哥德爾不完備定理

類比於羅素悖論

可以簡單的證明如下：

假設存在一個函數bool check(code c,data d)，可以對輸入的code c在data d上進行判斷，如果死循環則返回true，反之返回false，那麼我們可以構造一個新函數

bool new_check(code c) { if(check(c,c)) return true; while(1); return false; }

那麼對於new_check(new_check)就會造成矛盾:

如果new_check會死循環，則說明check(new_check)返回了false，說明new_check不會死循環

如果new_check不會死循環，則說明check(new_check)返回了true，說明new_check會死循環

如果去掉任意兩個字這個程序就有可能寫出來，但是加上任意兩個字就思密達了，核心涉及到自我指涉和自我否定。

停機問題有明確的適用條件，即：

1. 圖靈機是有無限存儲容量（無限長磁帶）的。

2. 判定和被判定程序都運行在圖靈機上。

在此前提下，停機問題的證明才可以對任意判定程序構造一個（比它更長的）反例。

如果不滿足這兩個條件，比如被判定程序運行在一台給定的真實的計算機上（存儲容量有限），而判定程序運行在另一台（存儲容量更大的）計算機上，則停機問題是trivial的：

假設被判定程序運行在總狀態數（CPU狀態+存儲，或狀態機+磁帶對於圖靈機）為2^K的計算機上，那麼顯然從任意狀態開始，在2^K步內要麼停機，要麼至少兩次到達同一狀態而死循環。那麼在另一台有2^(K+1)+C存儲的計算機上可以構造判斷程序如下：

def halt?(s):

c=0

while c&<2^K:

s=next_state(s)

if halt_state(s):

return true

c+=1

return false

這是著名的「停機問題」，最直觀易懂的證明是「對角線法」。

已知任何一段程序都可以用一段有限長度二進位01字元串表示 $x_{11} x_{12} dots x_{1n} dots$ ，其結果（停機與否），可以用一個額外01字元來表示，假定，該問題可判定，即存在一個程序F $F(x_{11} x_{12} dots x_{1n} dots) = {0,1}$ ，其對於所有程序判別結果可存在矩陣中表示如下

（該矩陣就是F的表現形式，前m-1項為程序內容，最後一項為F的判定結果）

下面開始構造F無法判定的反例

構造新的一行，該行第i個元素與F矩陣中的F_{ii}相反。
該新行不可能與第一行相同，因為它們第一個元素不同。
該新行不可能與第二行相同，因為它們第二個元素不同。
該新行不可能與第[i] 行相同，因為它們第[i] 個元素不同。
該新行不屬於任何F能判別的程序，與前提F能判別所有程序矛盾！
不存在能判別所有程序的F

PS：離散學得比較好，或者對集合論熟悉的同學已經發現了，本質就是兩個cardinality不同，以至於無法含括。

假設存在這樣的停機判定程序A。

那麼我們首先寫出一個驗證哥德巴赫猜想的程序B。此程序對每一個大於等於4的偶數驗證是否符合哥德巴赫猜想。如果碰到不符合的偶數就退出，否則繼續迭代。

用A判定B是否停機，如果停機，則說明哥德巴赫猜想為假，否則為真。

類似，可以寫出任意個程序驗證某一數學猜想/命題（例如黎曼猜想，費馬大定理 etc）的正確性，再用A去證明/證偽該命題（也就是我們發現了這個世界的bug），根據常識可知A不存在。

建議學習計算理論這本書

不可判斷

See Rice#x27;s theorem - Wikipedia

你可以去看看劉未鵬的《暗時間》一書。裡面在後面有一章講到這個問題。網上搜一下應該能找到他的博客

名字叫康托爾、哥德爾、圖靈——永恆的金色對角線

讀他的書很能體會思維的樂趣