是否存在一種演算法可以隨機生成乙個自然數？

1樓：楊玉皓

不存在。目前電腦隨機是用感覺到環境細微變化得到乙個數，然後帶入特殊公式運算得到一系列數。都是有根據得來的。只有量子計算機才有可能產生真正的隨機數

2樓：

在有限時間內能夠輸出的，一定是有限位數的。

所以不存在。

你說不用輸出？

那怎麼測呢？

理論證明也一樣啊，有限時間內所能取的結果的集合一定是有限的。自然數有無限多。

3樓：Yves S

現有的回答並沒有意識到題主在問乙個什麼樣的問題。

隨機不意味著均勻分布。幾何分布、二項分布都是隨機整數的分布，但是並不均勻。

因此，隨機生成整數也並不一定要求乙個有限的範圍。幾何分布就沒有範圍。

真隨機與偽隨機也不重要。純演算法層面當然做不到真隨機，但是通過硬體生成真隨機數已經很常見。

換句話說，只要你給我乙個自然數上的概率測度，我就能把它實現出來。此演算法依概率1在有限步內終止。

但是！！！

前提是「乙個概率測度」，而題主給的密度的定義，是乙個有限可加測度。概率測度是總質量為1的測度，而測度...它要求可數可加性。換句話說，乙個有限可加測度很可能連測度都不是。

所以題主的問題等價於，問題中定義的密度，是否在實際上是乙個概率測度？依定義，總質量為1不是問題。所以問題又等價於，這麼定義的密度，可不可以是可數可加的？

答案是否定的。具體來說，可以證明，對於問題中定義的密度，其在任何乙個有限集上的值為0。特別地，在任何乙個單獨的自然數上的值也為0。

具體證明不太短我就不寫了。但是可以看出，這與「密度」的直觀含義是相符的。

所以結論是不能，原因是題主給出的密度並不是乙個概率測度。換句話說，如果在任何乙個單點集上取值的概率都等於其密度，那麼取任何乙個點的概率都是0。這樣的分布不構成概率分布，因此沒法按照它隨機取自然數。

注意，儘管題主要求的密度實際上是「1到n上的均勻分布」當n趨於無窮時的乙個某種特定意義下的極限，但是這是需要證明的。問題問的是「按照定義的密度取概率」，而不是「按自然數上的均勻分布取概率」，所以「自然數上的均勻分布不存在」並不是乙個完整的回答。

4樓：

存在啊，這個世界既是確定的，又是隨機的。你只要給系統乙個數字，系統返給你乙個數字。你給系統同乙個數字，系統給你另外乙個數字。

你給系統無數個數字，系統返給你無數個數字，這些數字沒有統計規律，那麼就可以認為這些數字是隨機的。這個系統是混沌的。比如你取乙個無理數，不停的往後計算，你知道在某一位他是確定的，但是，在算出來之前你又不知道他是幾。

再讓這個數字跟現在的時間，滑鼠的位置等這種即時改變的數字作為種子，就可以得到乙個隨機數了。

5樓：暮無井見鈴

我認為不存在。

如果說是以概率1停止的演算法，則其所生成的自然數必定服從某個分布。然而自然數集上不存在均勻分布。

就 Q5 補充下。

若某個機器對於所有程式都能停機，那麼停機問題不會產生悖論。這個機器判定自身上的某個程式和輸入能否停機時，直接輸出 true 即可，不導致矛盾。

反過來說，若乙個機器上能有不停機的程式和輸入，則它無法判定某些程式在自身上是否能停機。

6樓：王贇 Maigo

一種「演算法」為：先在 0~9 中均勻取乙個數作為個位，然後再在 0~9 中均勻取乙個數作為十位，然後再在 0~9 中均勻取乙個數作為百位，如此迴圈無盡。

很明顯這種「演算法」的乙個 bug 是執行時間無限。但這沒辦法，因為你的演算法要能輸出無窮多種結果，那自然也就需要無窮多步操作了。

那為什麼「在 0 和 1 之間取乙個隨機實數」就能在有限的時間內完成呢？其實它是放棄了無限的精度，這樣輸出結果就只有有限多種了。但是「隨機自然數」跟「隨機實數」不一樣，它沒法通過放棄精度來把輸出結果由無限多種變為有限多種，所以不存在步驟有限的演算法。