更改

[[文件:伯努利图灵机示意图.png|居中|无框|500x363像素]]

[[文件:伯努利图灵机示意图.png|居中|无框|500x363像素]]

[[伯努利图灵机]]（Bernoulli-Turing machine，简称BTM）是确定性通用图灵机的一种扩展，通过引入随机数发生器，可以计算离散随机序列。它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。在运行过程中，伯努利图灵机按照常规图灵机的方式读取纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，当遇到与随机相关的规则时，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机源以一定的概率来决定执行哪一种操作。<math>

 

 

</math>下，最小模型的复杂度，[[伯努利图灵机]]（Bernoulli-Turing machine，简称BTM）是确定性通用图灵机的一种扩展，通过引入随机数发生器，可以计算离散随机序列。它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。在运行过程中，伯努利图灵机按照常规图灵机的方式读取纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，当遇到与随机相关的规则时，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机源以一定的概率来决定执行哪一种操作。<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,