概率自动机论
gail zidongjilun
概率自动机论
probabilistic automata theory
自动机论的次级学科，主要研究所处环境或内部具有（有限或无限的）随机因素的自动机。与非概率型自动机不同之处，是概率自动机的动作是随机的。为了给定概率自动机,首先必需规定在自动机处于某一状态,并向自动机输入某个字母的条件下，自动机下一动作（如状态转移，输出某个字母，改写字母等）的条件概率函数。其次是给定自动机的初始状态的概率分布──初始分布，一般用一个随机矢量＝(，，…，)表示，其中各个都是非负的，且相加之和等于1。是自动机状态的个数。 表示在开始时自动机处于第个状态的概率。包含有不可靠元件的数字电路和通信的信道都可以表示为概率自动机。
发展简况 早在40年代末，C.E.仙农在信息论的研究中，就提出了噪声信道的数学模型(见图[噪声信道])，它实际上就是一种概率自动机。50年代初，J.诺伊曼研究用不可靠元件构造可靠机器，这个问题发展成为现代的容错计算问题。但是直到50年代末，在R.W.阿西贝的著作中才给出一个形式定义的雏形。1963年M.O.拉宾比较严格地阐述了概率自动机的一些基本概念，并提出一些问题（如稳定性问题）。后来，A.帕兹等人的著作综述了这一方面的研究成果。60年代末至70年代，有更多的人进行了这方面的研究工作。
主要内容 与一般的自动机理论相平行的，有概率图灵机、概率时序机、概率识别器等方面的研究工作。这些工作一方面是推广自动机已有的结果；另一方面也提出不少新的问题，丰富了自动机论的内容。
概率图灵机 概率图灵机是图灵机的推广。它的形式定义可以用六元组=(,,,,,)给出。其中和分别是非空有限的状态集合和带字母集合。和 分别是输入字母集合和输出字母集合，且∪，∩=。是初始分布(,|,)是已知概率图灵机现在的状态,且注视在带字母 的条件下它的“下一动作”的概率。“下一动作”是下面三者之一。①[294-03]:用代替，且转移到状态；②=：读写头向右移一单元,且转移到状态；③＝：读写头向左移一单元，且转移到状态。
在概率图灵机的研究中，对可计算随机函数，给出了定义并对可计算函数及其运算也都作了研究，而且还证明了图灵机的许多研究结果在概率图灵机的情况下仍然成立。函数代入、原始递归、求极小等运算对可计算随机函数都是封闭的。限制在普通函数类的范围内，可以证明部分可计算随机函数中的普通函数，恰好是部分递归函数。从这个意义上看，把图灵机推广到概率图灵机的计算能力没有增大。也可以通过别的刻划方法，使概率图灵机所刻划的普通函数类，以部分递归函数类作为其真子类。在相对可计算性方面也有类似的结果。
概率时序机 它是时序机（见有限自动机论）的推广。其形式定义可以用五元组＝(，，，，)给出，其中，，，仍如前所述，是条件概率
(;|;)
,概率时序机被设想为理想化了的离散物理系统。它有有限个不同的内部状态，而且有下面两种性质：①如果现时状态是,输入字母,则(;|;)表示输出的字母是，并且下一时刻状态为的联合条件概率:②如果时序机开始时处于状态 ，并且输入字母依次是，，…，，则输出字母序列，，…，的概率是[294-06]仙农首先用这一数学模型描述离散噪声通信信道。因而关于概率时序机所得到的结果，既可以解释为非概率时序机理论所得结果的对应推广，又可以解释为有限状态通信信道的结构性质。
如果，，并且对于每一个正整数[295-01]对所有的[295-02]都成立，就称状态和是等价的。等价状态产生相同的“输入－输出关系”。研究状态等价的充分必要条件，是概率时序机理论的研究内容之一。
如同在非概率时序机情况，多余的等价状态可以被消除，从而得到一个化简了的时序机。对于概率时序机，它的化简了的形式不是唯一的，这一点和确定的时序机的情况有所不同。对于一个给定的概率时序机，可以找到一个寻求它的所有化简形式的计算方法。
概率有限识别器 只有输入没有输出的有限识别器的推广。它的形式定义可以用＝(，，，，)给出。其中[kg2]和仍表示输入字母表和状态集合，是初始分布，[295-03]是规定的终止状态集合。(│，)是当输入一个字母[kg1]时,状态从转移到的概率,简记为()()为以[kg1]()为元素的矩阵[295-0]是一个列矢量,它的维数等于内元素的个数,它相应于中的元素的分量等于1,其余的分量都是0,[295-07](…)=()()[9999]()[295-0]表示以为初始分布,输入字…后，状态进入终止集合 的概率。假定预先给定一个门限值(0≤＜1),则所有使得[295-07](…)＞的字…构成一个集合,称为概率有限识别器按切断点所识别的（或接受的）的随机语言,用集合的记号记为
[295-04]是中的字母所能构成的一切字的集合。
随机语言类包含有限识别器所识别的正则语言类作为其真子类，因而概率有限识别器是有限识别器的真推广。随机语言类对运算的封闭性，它的结构以及它与正则语言类的关系都是研究的重要内容。另一个问题是所谓稳定性问题。即对一个给定的概率识别器，转移概率的微小扰动所引起的(,)中变化情况的研究。
多阶段判决过程 概率自动机也可以用于多阶段判决过程。在这一过程中，从一个状态到另一状态的转移都附有一个条件概率和补偿因子假设对个状态的概率自动机从状态转移到状态的补偿因子是,则对于概率自动机在处一步转移中的补偿的数学期望值是
[295-05]由此可以求出在步之后的全部补偿。
概率自动机的熵 定义概率自动机的熵为
[295-06]其中 ()是自动机在步转移之后处于状态的概率。熵的概念可以用于模式识别和可靠性问题的研究。用概率自动机描述不可靠自动机时，熵可以作为有限自动机的可靠性的测度。可靠性随着熵的减小而增加，可靠自动机的熵是零。
概率自动机理论与信息论、可靠性理论、自学习理论和模式识别、控制论、程序设计和马尔可夫链的函数理论都有着密切的联系。图灵机，各型形式语言的概率性推广，具有概率性结构的树自动机，概率自动机与动态规划的关系，以及从范畴论观点对随机自动机的研究，都是一些有意义的研究课题。