1樓：hhh
因為可計算函式和自然數一樣多，而不可計算函式至少和實數一樣多。
證明為因為字元是能列舉的。我們把字元分三類，一是數字，二是符號，三是字母。
於是可計算函式的對應：
0 y=0 1 y=1 2 y=a 3 y=a+1 4 y=a+b 5 y=a-1……
然後字母，數字，符號全體編號。按1，2，3順序，然後先排y=0,然後就y=……，然後先排字母，數字，符號都在1以內的，接著排2以內的。當然，也要按項數，先排項數為1，再排項數為2，以此類推，這樣就能使全體可計算函式與自然數一一對應。
所以可計算函式與自然數等勢。
然而全體函式集的是不可數集的證明。
因為全體函式包括常值函式。假設全體函式可數，則常值函式可數，但因為實數不可數，所以常值函式是不可數的，所以全體函式是不可數的。
然後不可計算函式就是全體函式中去掉可計算函式的集合。因為全體函式不可數而可計算函式可數，而不可數集去掉可數集後還是不可數集，因此不可計算函式不可數。
2樓：
關鍵在於定義可計算的函式，如果我們對定義好的函式進行乙個編碼的話，比如採用素數指數編碼（記函式的第i個字元二進位制編碼值為v，對應第i個素數的v次方，然後將所有字元對應的編碼相乘），那麼得到可計算函式與自然數集的乙個子集一一對應，而不可計算的函式包括了不可定義數，這個與實數集相對應，所以可計算函式要少於不可計算函式
3樓：黃玄
嚴謹的證明的話，可以使用「形式語言」（Formal language）來證明：
在可計算理論和計算複雜度理論中，每個「計算問題」都被描述為乙個乙個「形式語言」，即字串的集合。比如對於判斷乙個圖是否是無向連通圖這個問題：我們可以寫為乙個描述所有無向連通圖的集合：
由於圖靈機只能接受字串，所以這裡的尖括號表示對圖的「編碼」。出於簡單，我們全部使用現實計算機所使用的字母表 ，所以「編碼」即乙個物件的二進位制字串描述。
如果我們能構造出乙個圖靈機來「決定」這個「形式語言」，即可以判斷乙個「輸入」是否屬於這個集合（membership 與 non-membership），那麼我們可以說我們用「圖靈機」描述了乙個「演算法」來計算這個問題，而這個「計算問題」所對應的函式是「可計算的」，否則是「不可計算的」。（注1）
那麼，如果我們有乙個包含了所有「可計算函式」的集合，這個集合會有多大呢？
由於所有「可計算函式」總有乙個對應的「圖靈機」來計算它
每乙個「圖靈機」都可以被「編碼」為乙個不同的 0、1 序列，比如 000，010...
0、1 序列、即二進位制，總是可以被轉換為乙個十進位制數的
所以，我們這個集合實際上是與整數集 一樣大（等勢）的，我們把這個集合表示為 。 易知 是「無窮可數（countably infinite）」的，所以我們有無窮可數個「可計算函式」（注2）。
而「計算問題」有多少個呢？
這個問題可以等同於，我們有多少個形如 這樣的 0，1 序列的集合？即 這個集合有多少個子集？用數學語言描述就是求 的冪集的勢 。
由於 與 是等勢的，所以這個問題等價於求 的大小。根據 Cantor's theorem，乙個「無窮可數」的集合的冪集是「無窮不可數（uncountably infinite）」的。（注3）
根據 Cantor's theorem，「無窮不可數集」要比「無窮可數集」大。
同時，「無窮不可數集」減去「無窮可數集」後仍然是「無窮不可數集」。（注4）
所以，「不可計算函式集」，即「計算問題集」與「可計算函式集」的差，仍是「無窮不可數集」，仍比是為「無窮可數集」的「可計算函式集」大。
因此，「不可計算的函式」比「可計算的函式」多。
證畢。注：
「可計算函式」是演算法的直覺說法，「邱奇－圖靈論題」猜想任何在演算法上可計算的問題同樣可以由圖靈機計算。但圖靈機並不是唯一的計算模型，其他計算模型包括「Lambda 運算元」、「 - 遞迴函式」等，它們在計算能力上都是與「圖靈機」等價的。
證明「所有可計算函式」的集合是「無窮可數集」的方式有很多，只要找到任意乙個與「自然數集」的「雙射」即可
也可以直接用康托的對角線法（Cantor's diagonal argument）證明「所有計算問題」的集合是「無窮不可數集」
可以用反證法得證
知乎能用 LaTex 了好評
4樓：
結論基礎主要是說它的地位，而未必是指你能很容易想出證明。（模擬代數基本定理，多項式方程總有複數根。）
不知道你從哪門課程看到這個結論，所以不能肯定這個結論的證明是否對於你的背景知識來說是容易的。
當然，也容易給出乙個簡單的證明。
概要是，任一可計算函式都可以對應於乙個圖靈機（或者程式）來計算它，這個圖靈機當然只有有限個狀態和有限大小的轉移函式（或者這個程式只有有限長），所以可以按固定方式唯一編碼為乙個正整數，於是就建立了從任一可計算函式到正整數的對映，因此可計算函式是可數的。
另一方面，顯然函式是不可數的，例如能輸出實數 t 任意第 x 位的函式族 T(x) 就有實數那麼多個，實數不可數，所以不可計算函式是作為可計算函式的補自然不可數。
然後由康託定理，不可數集比可數集大。
什麼叫不可計算數？
Narc 問問題前查查維基 可計算數 英語 computable numbers 是數學名詞，是指可用有限次 會結束的演算法計算到任意精確度的實數。可計算數也被稱為遞迴數 遞迴實數或可計算實數。 Xyan Xcllet 首先，乙個實數 若稱作是可計算的 也就是說，這個實數可以通過乙個圖靈機在有限的通...
為什麼能行可計算的就是圖靈可計算的（遞迴的）？
如果我沒理解錯的話，題主想要問的實際上就是丘奇 圖靈論題 Church Turing Thesis 為什麼成立。丘奇 圖靈論題簡單地說就是 乙個自然數上的函式 是能行可計算的 effectively computable 當且僅當它是圖靈可計算的 Turing computable 其中，能行可計算...
1 2 的所有正整數冪之和是 可計算的 嗎？
隔壁你王哥 這讓我想起小學的乙個題，當時覺得這可真是太厲害因為 1 3 0.3333.1 3 3 1 所以有 0.999.1 我來隨便瞎說一點 乙個乙個加肯定能加完，做法 用一秒算加1，用半秒算加1 2，用四分之一秒算加1 4，這樣你一秒就全算完啦 琉年 有點明白了，自答 應該是說，只要存在演算法就...