伯努利图灵机 - 版本历史

刘易明：/* 定义与公式 */

2025-02-11T09:03:16Z

定义与公式

刘易明：/* 定义与公式 */

2025-02-11T08:53:06Z

定义与公式

刘易明：/* 定义与公式 */

2025-02-11T08:34:37Z

定义与公式

刘易明：/* 定义与公式 */

2025-02-11T08:32:48Z

定义与公式

2025年2月11日 (二) 08:31 刘易明

2025-02-11T08:31:59Z

刘易明：/* 定义与公式 */

2025-02-11T08:23:09Z

定义与公式

刘易明：/* 定义与公式 */

2024-12-24T05:16:21Z

定义与公式

2024年12月24日 (二) 02:12 刘易明

2024-12-24T02:12:25Z

2024年12月24日 (二) 02:10 刘易明

2024-12-24T02:10:41Z

刘易明：建立内容为“伯努利图灵机（BTM）是一种对基本图灵机模型进行概率性推广的计算模型，在计算理论中具有重要意义，它通过与信息源（…”的新页面

2024-12-24T01:56:30Z

建立内容为“伯努利图灵机（BTM）是一种对基本图灵机模型进行概率性推广的计算模型，在计算理论中具有重要意义，它通过与信息源（…”的新页面

新页面

伯努利图灵机（BTM）是一种对基本图灵机模型进行概率性推广的计算模型，在计算理论中具有重要意义，它通过与信息源（如热浴）的连接，引入了随机性，从而为研究计算和信息处理提供了更广泛的视角。以下结合PART II部分的相关内容，对其详细说明：
1. **定义与结构**
- **基本结构**：伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。
- **与信息源的连接**：BTM通过与一个信息源（如文中提到的表示为“沸腾水锅”的热浴）相连，引入了随机性。这种连接使得BTM在计算过程中能够利用随机信息，从而扩展了其计算能力和表达能力。
2. **计算能力与特点**
- **离散随机顺序计算模型**：BTM定义了最一般的离散随机顺序计算模型，它能够处理具有随机性的信息，并在计算过程中进行随机决策。这使得它在模拟和分析随机过程、不确定性系统以及需要处理随机信息的场景中具有重要作用。
- **与确定性图灵机的对比**：与确定性图灵机不同，BTM的计算过程不仅取决于输入和当前状态，还受到随机信息源的影响。这种随机性使得BTM能够生成更丰富多样的计算结果，并且在某些情况下，能够更有效地处理复杂的计算任务。
3. **在研究中的应用**
- **对比复杂性度量**：在计算理论中，BTM被用于对比确定性复杂度和统计复杂度。通过将词汇表基于可以猜测的图灵机（即BTM），可以定义统计复杂度，从而更好地理解计算过程中的结构和随机性之间的关系。
- **分析自然过程**：在分析自然过程中的计算结构时，BTM提供了一种框架，用于理解和量化系统中的信息处理和结构。例如，在研究非线性动力学系统、隐藏马尔可夫模型和细胞自动机等复杂系统时，BTM可以帮助研究人员更好地理解系统中的内在计算机制、复杂性和随机性的相互作用。

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

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

@@ 第3行： / 第3行： @@
 == 定义与公式 ==
-伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制器和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。
+伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制器和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。热源为随机性的输入来源，流程见下图：
 [[文件:伯努利图灵机示意图.png|居中|无框|500x363像素]]

@@ 第3行： / 第3行： @@
 == 定义与公式 ==
-伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。
+伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制器和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。
 [[文件:伯努利图灵机示意图.png|居中|无框|500x363像素]]

@@ 第4行： / 第4行： @@
 == 定义与公式 ==
 伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。
-[[文件:伯努利图灵机示意图|缩略图]]
 伯努利图灵机的公式为

←上一版本		2024年12月24日 (二) 05:16的版本
第34行：		第34行：

	相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。		相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。
−
−	下图展示了柯式复杂度和统计复杂度随着序列从简单周期性到完全随机的过程中的差异。如图(a)所示，柯式复杂度是过程中随机性的单调递增函数。相反，统计复杂度在两个极端点上均为零，并在中间达到最大值（见图(b)）。它基于这样的观点：随机性在统计上是简单的，一个完全随机的过程具有零统计复杂度。周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。
−	~~[[文件:复杂度比较.jpg\|居中\|无框\|600x600像素\|~~
−

	]]		]]

@@ 第15行： / 第15行： @@
 <math>
 C_{\mu}(x)
-</math>是统计复杂度<ref name=':15' />，表示时间序列<math>
+</math>是统计复杂度，表示时间序列<math>
+x
 </math>的复杂性度量。它反映了在给定精度<math>
@@ 第29行： / 第29行： @@
 </math>的最简单形式，且在该模型中尽量减少其复杂性。<math>
 \left\|⋅\right\|
-</math>这个符号表示对模型复杂度的量化。由于内部模型作为一种图灵机，本身也是用字符串（因果态）来描述，所以可以用长度、香农熵等指标来度量内部模型的复杂度。当我们使用香农熵来刻画内部模型的复杂度时，我们可以给出对于观测序列来说，伯努利图灵机定义下的统计复杂度通常是不可计算的，但它有一个等价的关于香农熵的可计算定义为<ref name=':15' />：
+</math>这个符号表示对模型复杂度的量化。由于内部模型作为一种图灵机，本身也是用字符串（因果态）来描述，所以可以用长度、香农熵等指标来度量内部模型的复杂度。当我们使用香农熵来刻画内部模型的复杂度时，我们可以给出对于观测序列来说，伯努利图灵机定义下的统计复杂度通常是不可计算的，但它有一个等价的关于香农熵的可计算定义为：
 <math>C_\mu(\mathcal{x})\equiv H[\mathcal{S}] </math>，其中<math>\mathcal{S} </math>为观测数据<math>\mathcal{x} </math>的因果态集合。

@@ 第1行： / 第1行： @@
-伯努利图灵机（BTM）是一种对基本图灵机模型进行概率性推广的计算模型，在计算理论中具有重要意义，它通过与信息源（如热浴）的连接，引入了随机性，从而为研究计算和信息处理提供了更广泛的视角。以下结合PART II部分的相关内容，对其详细说明：
-. **定义与结构**
+伯努利图灵机（BTM）是一种对基本图灵机模型进行概率性推广的计算模型，在计算理论中具有重要意义，它通过与信息源（如热浴）的连接，引入了随机性，从而为研究计算和信息处理提供了更广泛的视角。
-    - **基本结构**：伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。
-    - **与信息源的连接**：BTM通过与一个信息源（如文中提到的表示为“沸腾水锅”的热浴）相连，引入了随机性。这种连接使得BTM在计算过程中能够利用随机信息，从而扩展了其计算能力和表达能力。
+== 定义与公式 ==
-. **计算能力与特点**
-    - **离散随机顺序计算模型**：BTM定义了最一般的离散随机顺序计算模型，它能够处理具有随机性的信息，并在计算过程中进行随机决策。这使得它在模拟和分析随机过程、不确定性系统以及需要处理随机信息的场景中具有重要作用。
-    - **与确定性图灵机的对比**：与确定性图灵机不同，BTM的计算过程不仅取决于输入和当前状态，还受到随机信息源的影响。这种随机性使得BTM能够生成更丰富多样的计算结果，并且在某些情况下，能够更有效地处理复杂的计算任务。
+伯努利图灵机是一种确定性图灵机的扩展，它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入（输出）磁带单元只能按顺序读取（写入）一次，中间处理和存储由工作磁带提供，工作磁带允许双向访问其内容。
-. **在研究中的应用**
-    - **对比复杂性度量**：在计算理论中，BTM被用于对比确定性复杂度和统计复杂度。通过将词汇表基于可以猜测的图灵机（即BTM），可以定义统计复杂度，从而更好地理解计算过程中的结构和随机性之间的关系。
+伯努利图灵机的公式为
-    - **分析自然过程**：在分析自然过程中的计算结构时，BTM提供了一种框架，用于理解和量化系统中的信息处理和结构。例如，在研究非线性动力学系统、隐藏马尔可夫模型和细胞自动机等复杂系统时，BTM可以帮助研究人员更好地理解系统中的内在计算机制、复杂性和随机性的相互作用。