如何證明不可計算的函數比可計算的函數多？

12-23

在上大學計算機的MOOC是看到的，說是一個基礎結論，可這是怎麼被證明出來的我卻沒什麼頭緒

嚴謹的證明的話，可以使用「形式語言」（Formal language）來證明：

在可計算理論和計算複雜度理論中，每個「計算問題」都被描述為一個一個「形式語言」，即字元串的集合。比如對於判斷一個圖是否是無向連通圖這個問題：我們可以寫為一個描述所有無向連通圖的集合：

$A = { langle G angle vert G ext{ is a connected undirected graph}}$

由於圖靈機只能接受字元串，所以這裡的尖括弧表示對圖的「編碼」。出於簡單，我們全部使用現實計算機所使用的字母表 $Sigma = {0, 1}$ ，所以「編碼」即一個對象的二進位字元串描述。

如果我們能構造出一個圖靈機來「決定」這個「形式語言」，即可以判斷一個「輸入」是否屬於這個集合（membership 與 non-membership），那麼我們可以說我們用「圖靈機」描述了一個「演算法」來計算這個問題，而這個「計算問題」所對應的函數是「可計算的」，否則是「不可計算的」。（注1）

那麼，如果我們有一個包含了所有「可計算函數」的集合，這個集合會有多大呢？

由於

所有「可計算函數」總有一個對應的「圖靈機」來計算它
每一個「圖靈機」都可以被「編碼」為一個不同的 0、1 序列，比如 000，010...
0、1 序列、即二進位，總是可以被轉換為一個十進位數的

所以，我們這個集合實際上是與整數集 $Z$ 一樣大（等勢）的，我們把這個集合表示為 $Sigma^{*}$ 。易知 $Z$ 是「無窮可數（countably infinite）」的，所以我們有無窮可數個「可計算函數」（注2）。

而「計算問題」有多少個呢？

這個問題可以等同於，我們有多少個形如 ${000, 010}$ 這樣的 0，1 序列的集合？即 $Sigma^{*}$ 這個集合有多少個子集？用數學語言描述就是求 $Sigma^{*}$ 的冪集的勢 $|P( Sigma^{*} )|$ 。

由於 $Sigma^{*}$ 與 $Z$ 是等勢的，所以這個問題等價於求 $|P(Z)|$ 的大小。根據 Cantor"s theorem，一個「無窮可數」的集合的冪集是「無窮不可數（uncountably infinite）」的。（注3）

根據 Cantor"s theorem，「無窮不可數集」要比「無窮可數集」大。

同時，「無窮不可數集」減去「無窮可數集」後仍然是「無窮不可數集」。（注4）

所以，「不可計算函數集」，即「計算問題集」與「可計算函數集」的差，仍是「無窮不可數集」，仍比是為「無窮可數集」的「可計算函數集」大。

因此，「不可計算的函數」比「可計算的函數」多。

證畢。

註：

「可計算函數」是演算法的直覺說法，「邱奇－圖靈論題」猜想任何在演算法上可計算的問題同樣可以由圖靈機計算。但圖靈機並不是唯一的計算模型，其他計算模型包括「Lambda 運算元」、「 $mu$ - 遞歸函數」等，它們在計算能力上都是與「圖靈機」等價的。
證明「所有可計算函數」的集合是「無窮可數集」的方式有很多，只要找到任意一個與「自然數集」的「雙射」即可
也可以直接用康托的對角線法（Cantor"s diagonal argument）證明「所有計算問題」的集合是「無窮不可數集」
可以用反證法得證
知乎能用 LaTex 了好評

結論基礎主要是說它的地位，而未必是指你能很容易想出證明。（類比代數基本定理，多項式方程總有複數根。）
不知道你從哪門課程看到這個結論，所以不能肯定這個結論的證明是否對於你的背景知識來說是容易的。

當然，也容易給出一個簡單的證明。
概要是，任一可計算函數都可以對應於一個圖靈機（或者程序）來計算它，這個圖靈機當然只有有限個狀態和有限大小的轉移函數（或者這個程序只有有限長），所以可以按固定方式唯一編碼為一個正整數，於是就建立了從任一可計算函數到正整數的映射，因此可計算函數是可數的。
另一方面，顯然函數是不可數的，例如能輸出實數 t 任意第 x 位的函數族 T(x) 就有實數那麼多個，實數不可數，所以不可計算函數是作為可計算函數的補自然不可數。
然後由康托定理，不可數集比可數集大。

關鍵在於定義可計算的函數，如果我們對定義好的函數進行一個編碼的話，比如採用素數指數編碼（記函數的第i個字元二進位編碼值為v，對應第i個素數的v次方，然後將所有字元對應的編碼相乘），那麼得到可計算函數與自然數集的一個子集一一對應，而不可計算的函數包括了不可定義數，這個與實數集相對應，所以可計算函數要少於不可計算函數

一一對應的映射，和集合概念？

具體證明我不會。。理論方法應該是這個思路吧。