我的博客已经搬家到 xiongbox.com 欢迎访问熊伟的博客！

本文永久链接 http://xiongbox.com/概率自动机论的简单小结/

1.概率自动机论主要研究所处环境或内部具有（有限或无限的）随机因素的自动机。与非概率型自动机不同之处，是概率自动机的动作是随机的。为了给定概率自动机，首先必需规定在自动机处于某一状态，并向自动机输入某个字母的条件下，自动机下一动作（如状态转移，输出某个字母，改写字母等）的条件概率函数。

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

3.如同在非概率时序机情况，多余的等价状态可以被消除，从而得到一个化简了的时序机。对于概率时序机，它的化简了的形式不是唯一的，这一点和确定的时序机的情况有所不同。对于一个给定的概率时序机，可以找到一个寻求它的所有化简形式的计算方法。随机语言类包含有限识别器所识别的正则语言类作为其真子类，因而概率有限识别器是有限识别器的真推广。随机语言类对运算的封闭性，它的结构以及它与正则语言类的关系都是研究的重要内容。

4.概率自动机也可以用于多阶段判决过程。在这一过程中，从一个状态到另一状态的转移都附有一个条件概率和补偿因子。熵的概念可以用于模式识别和可靠性问题的研究。用概率自动机描述不可靠自动机时，熵可以作为有限自动机的可靠性的测度。可靠性随着熵的减小而增加，可靠自动机的熵是零。概率自动机理论与信息论、可靠性理论、自学习理论和模式识别、控制论、程序设计和马尔可夫链的函数理论都有着密切的联系。图灵机，各型形式语言的概率性推广，具有概率性结构的树自动机，概率自动机与动态规划的关系，以及从范畴论观点对随机自动机的研究，都是一些有意义的研究课题。