数学小百科－－-概率自动机论

 的条件下它的“下一动作”的概率。“下一动作”是下面三者之一。①[294-03]

:用

代替

，且转移到状态

;②

=

：读写头向右移一单元,且转移到状态

;③

=

：读写头向左移一单元，且转移到状态

。

在概率图灵机的研究中，对可计算随机函数，给出了定义并对可计算函数及其运算也都作了研究，而且还证明了图灵机的许多研究结果在概率图灵机的情况下仍然成立。函数代入、原始递归、求极小等运算对可计算随机函数都是封闭的。限制在普通函数类的范围内，可以证明部分可计算随机函数中的普通函数，恰好是部分递归函数。从这个意义上看，把图灵机推广到概率图灵机的计算能力没有增大。也可以通过别的刻划方法，使概率图灵机所刻划的普通函数类，以部分递归函数类作为其真子类。在相对可计算性方面也有类似的结果。

概率时序机  它是时序机(见有限自动机论)的推广。其形式定义可以用五元组

=(

，

，

，

，

)给出，其中

，

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]  下一页