熵重新包装

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返回到输入流有效的解决方案。然而，我无法说服我的自我，即使是已知的输出范围形式也是如此......