1樓：豬鼻蛇
既然 @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 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.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我都會寫的更舒服一點。
2樓：zr scat
這個問題等價圖靈停機問題
模擬於哥德爾不完備定理
模擬於羅素悖論
可以簡單的證明如下：
假設存在乙個函式bool check(code c,data d)，可以對輸入的code c在data d上進行判斷，如果死迴圈則返回true，反之返回false，那麼我們可以構造乙個新函式
bool new_check(code c)那麼對於new_check(new_check)就會造成矛盾:
如果new_check會死迴圈，則說明check(new_check)返回了false，說明new_check不會死迴圈
如果new_check不會死迴圈，則說明check(new_check)返回了true，說明new_check會死迴圈
3樓：Lyken
這是著名的「停機問題」，最直觀易懂的證明是「對角線法」。
已知任何一段程式都可以用一段有限長度二進位制01字串表示，其結果（停機與否），可以用乙個額外01字元來表示，假定，該問題可判定，即存在乙個程式F ，其對於所有程式判別結果可存在矩陣中表示如下
（該矩陣就是F的表現形式，前m-1項為程式內容，最後一項為F的判定結果）
下面開始構造F無法判定的反例
構造新的一行 ，該行第i個元素與F矩陣中的F_相反。
該新行不可能與第一行相同，因為它們第乙個元素不同。
該新行不可能與第二行相同，因為它們第二個元素不同。
該新行不可能與第[i] 行相同，因為它們第[i] 個元素不同。
該新行不屬於任何F能判別的程式，與前提F能判別所有程式矛盾！
不存在能判別所有程式的F
PS：離散學得比較好，或者對集合論熟悉的同學已經發現了，本質就是兩個cardinality不同，以至於無法含括。
4樓：Belleve
通用的不存在， @陳碩 的鏈結裡面就是，另外從這個可以得到很多「神奇」演算法也不存在比如判斷外延相等性……
不過另一方面，保守地判斷某個程式（或者 Lambda 項）必然終止的演算法還是有不少的。對此類演算法它們可以得出以下兩者結論之一：
此程式必然終止
此程式可能有死迴圈 / 無限遞迴
乙個經典的例子就是 Foetus 終止分析，它會檢查所有遞迴呼叫看是否每次遞迴的資料結構都比原來更小。
5樓：02xiaoma
你可以去看看劉未鵬的《暗時間》一書。裡面在後面有一章講到這個問題。網上搜一下應該能找到他的部落格
名字叫康托爾、哥德爾、圖靈——永恆的金色對角線
讀他的書很能體會思維的樂趣
6樓：魯哈花
這不就是著名的停機問題嗎，關於這個問題有個漂亮的證明方法，是圖靈給出的。
停機問題、Chaitin常數與萬能證明方法
康托爾、哥德爾、圖靈——永恆的金色對角線(rev#2)
「不存在」本身，是否也是一種存在？
Loace汐x偌 如果一切都不存在了，那至少還有一種東西存在，那就是 不存在 本身。如果連 不存在 都不存在了，那意味著一切可能存在都必須存在，可 不存在 也是一種存在，所以推出 不存在 仍然存在。可是 不存在 如果存在的話，那 不存在 就不存在了，因為還有 不存在 的存在。所以這是個悖論。不存在 ...
科學可以證明乙個東西不存在嗎？
老熊 不能，科學是我們去認知世界的工具，任何工具都是有侷限性的。科學也許可以說明乙個東西是不必要的，但無法證明是不存在的。比如，上帝或造物主是否存在？我們也許可以說，在我們目前的體系中，也許不必要有造物主這一設定，但我們可能永遠無法證明造物主是不存在的。再比如平行宇宙 白雲龍 如果你能給出嚴格的定義...
如果人類不存在繁衍，而是一種永生存在，那麼還會持續進化出新社會嗎？
放進書包裡面 這個假設是不存在的，生物是不可能永生的，除非生物進行了環形延續，就是一開始無數種細菌組合在一起形成了人類，那就是誕生嬰兒青年成年老年嬰兒。但這也不是永生，如果是按照這種理論的話，人類也不會進化出新的社會，我這裡把這種延續下的人類稱為新人，新人如果是這樣存在的話，新人要想讓自己這個物種能...