熵重新包裝

Question

我一直在折騰一個機器的概念性想法（如在圖靈機）和我想知道是否有任何工作已經完成在這個或相關的主題。

這個想法是一個機器，它採用一個熵流，並在任何範圍內發出隨機符號而不會丟失任何熵。

我會隆重的說這是一個非常嚴格的描述，所以我舉個例子：假設我有一個在1到n範圍內的隨機符號的生成器，我希望能夠請求一個符號任何給定的範圍，首先1至12然後1至1234。 （爲了保持可行性，我將只考慮確定性機器，在給定相同輸入流和請求的情況下，它總是會給出相同的輸出。）一個必要的約束是輸出包含至少與輸入一樣多的熵。然而，我最感興趣的約束是機器只讀入儘可能多的熵。

E.g.如果要求令牌的範圍爲1至S1, S2, S3, ... Sm，它只會消耗ceiling(sum(i = 1 to m, log(Si))/log(n))輸入令牌。

This question詢問如何在滿足第一個約束的同時執行此轉換，但在第二個約束上做得非常糟糕。

Answer 1

好吧，我仍然不確定我是否追隨你想要的。它聽起來好像要的功能

˚F：我→ö

其中輸入是字母表的符號的強隨機（均勻分佈等）序列我 = {1 ... n}。 （因此，一系列隨機自然數≤n。）輸出是O = {1 .. m}上的另一個序列，並且您希望該序列具有與輸入一樣多的熵。

好的，如果我有這個權利，首先，如果m < n，你不能。如果米<Ñ然後LG米 < LG Ñ，所以該組的輸出符號的熵更小。

如果米≥Ñ，然後就可以通過平凡只是選擇的^我第元件做{1 ..米}。熵將是相同的，因爲可能的輸出符號的數量是相同的。儘管在整個集合中均勻分佈的意義上它們不會是「隨機的」，但是，因爲必然（一個原則）某些符號根本不會被選中。

如果，在另一方面，你會得到滿意的具有一個隨機序列{1 ..米}，則可以通過選擇使用從隨機源的輸入適當的僞隨機數發生器做作爲種子。

Answer 2

我的電流通過它：

通過添加下列限制：你事先知道範圍的序列{S1，S2，S3，...，S}，比使用基本的翻譯用非恆定的基地可能的工作：

1. 從輸入查找Sp = S1 * S2 * S3 * ... * Sn
2. 提取m=cealing(log(Sp)/log(n))方面{R1, R2, R3, ..., Rm}
3. 查找X = R1 + R2*n + R3*n^2 + ... + Rm*n^(m-1)
4. 改革X作爲O1 + S1*O2 + S1*S2*O3 + ... Sn*On + x其中1 <= Oi <= Si

這可能是可轉化成一個值在同一時間推X返回到輸入流有效的解決方案。然而，我無法說服我的自我，即使是已知的輸出範圍形式也是如此......