数学百科知识专题：概率自动机论

 分别是输入字母集合和输出字母集合，且∪，∩=。是初始分布(,",)是已知概率图灵机现在的状态,且注视在带字母 的条件下它的“下一动作”的概率。“下一动作”是下面三者之一。①[294-03]:用代替，且转移到状态；②=：读写头向右移一单元,且转移到状态；③＝：读写头向左移一单元，且转移到状态。
   在概率图灵机的研究中，对可计算随机函数，给出了定义并对可计算函数及其运算也都作了研究，而且还证明了图灵机的许多研究结果在概率图灵机的情况下仍然成立。函数代入、原始递归、求极小等运算对可计算随机函数都是封闭的。限制在普通函数类的范围内，可以证明部分可计算随机函数中的普通函数，恰好是部分递归函数。从这个意义上看，把图灵机推广到概率图灵机的计算能力没有增大。也可以通过别的刻划方法，使概率图灵机所刻划的普通函数类，以部分递归函数类作为其真子类。在相对可计算性方面也有类似的结果。

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