伯努利图灵机
跳到导航
跳到搜索
伯努利图灵机(BTM)是一种对基本图灵机模型进行概率性推广的计算模型,在计算理论中具有重要意义,它通过与信息源(如热浴)的连接,引入了随机性,从而为研究计算和信息处理提供了更广泛的视角。
定义与公式
伯努利图灵机(Bernoulli-Turing machine,简称BTM)是确定性通用图灵机的一种扩展,通过引入随机数发生器,可以计算离散随机序列。它包含输入磁带、输出磁带、有限状态控制单元和工作磁带。输入(输出)磁带单元只能按顺序读取(写入)一次,中间处理和存储由工作磁带提供,工作磁带允许双向访问其内容。热源为随机性的输入来源,简称随机数发生器,流程见下图:
上图的伯努利图灵机在运行过程中,伯努利图灵机按照常规图灵机的方式读取输入纸带上的符号和自身的当前状态,并依据内置的规则表进行操作。与普通图灵机不同的是,当遇到与随机相关的规则时,它会根据随机数发生器的采样结果来决定具体的执行路径。例如,在某个状态下,图灵机可能有两种可选的操作,普通图灵机根据确定的规则选择其中一种,而伯努利图灵机则通过随机数发生器以一定的概率来决定执行哪一种操作。[math]\displaystyle{ M_{\min }(x \mid \mathrm{BTM}) }[/math]这是在给定伯努利图灵机背景下的最小化模型[1]
- ↑ 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.