697
个编辑
更改
跳到导航
跳到搜索
第3行：
第3行： − 伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制器和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。热源为随机性的输入来源，流程见下图：+ − [[伯努利图灵机]]（Bernoulli-Turing machine，简称BTM）是确定性通用图灵机的一种扩展，通过引入随机数发生器，可以计算离散随机序列。它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。在运行过程中，伯努利图灵机按照常规图灵机的方式读取纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，当遇到与随机相关的规则时，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机源以一定的概率来决定执行哪一种操作。<math>+ − + − x − </math>的模式。这个模型是能够有效预测<math> − x − </math>的最简单形式，且在该模型中尽量减少其复杂性。<math> − \left\|⋅\right\| − </math>这个符号表示对模型复杂度的量化。由于内部模型作为一种图灵机，本身也是用字符串（因果态）来描述，所以可以用长度、香农熵等指标来度量内部模型的复杂度。当我们使用香农熵来刻画内部模型的复杂度时，我们可以给出对于观测序列来说，伯努利图灵机定义下的统计复杂度通常是不可计算的，但它有一个等价的关于香农熵的可计算定义为： − − <math>C_\mu(\mathcal{x})\equiv H[\mathcal{S}] </math>，其中<math>\mathcal{S} </math>为观测数据<math>\mathcal{x} </math>的因果态集合。 − − 相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。 − − ]]
→定义与公式
== 定义与公式 ==
== 定义与公式 ==
伯努利图灵机（Bernoulli-Turing machine，简称BTM）是确定性通用图灵机的一种扩展，通过引入随机数发生器，可以计算离散随机序列。它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。热源为随机性的输入来源，简称随机数发生器，流程见下图：
[[文件:伯努利图灵机示意图.png|居中|无框|500x363像素]]
[[文件:伯努利图灵机示意图.png|居中|无框|500x363像素]]
上图的伯努利图灵机在运行过程中，伯努利图灵机按照常规图灵机的方式读取输入纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，当遇到与随机相关的规则时，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机数发生器以一定的概率来决定执行哪一种操作。<math>
M_{\min }(x \mid \mathrm{BTM})
M_{\min }(x \mid \mathrm{BTM})
</math>这是在给定伯努利图灵机背景下的最小化模型<ref>C. H. Bennett. Dissipation, information, computational complexity, and the definition of organization. In D. Pines, editor, ''Emerging Syntheses in the Sciences''. Addison-Wesley,
</math>这是在给定伯努利图灵机背景下的最小化模型<ref>C. H. Bennett. Dissipation, information, computational complexity, and the definition of organization. In D. Pines, editor, ''Emerging Syntheses in the Sciences''. Addison-Wesley,
Redwood City, 1988.</ref>，用于捕捉序列<math>
Redwood City, 1988.</ref>