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

当今社会是一个高速发展的信息社会。生活在信息社会，就要不断地接触或获取信息。如何获取信息呢?阅读便是其中一个重要的途径。据有人不完全统计，当今社会需要的各种信息约有80%以上直接或间接地来自于图书文献。这就说明阅读在当今社会的重要性。还在等什么，快来看看这篇数学小百科---概率自动机论吧~

gail

 zidongjilun

概率自动机论

probabilistic automata theory

自动机论的次级学科，主要研究所处环境或内部具有(有限或无限的)随机因素的自动机。与非概率型自动机不同之处，是概率自动机的动作是随机的。为了给定概率自动机,首先必需规定在自动机处于某一状态,并向自动机输入某个字母的条件下，自动机下一动作(如状态转移，输出某个字母，改写字母等)的条件概率函数。其次是给定自动机的初始状态的概率分布──初始分布，一般用一个随机矢量

=(

，

，…，

)表示，其中各个

都是非负的，且相加之和等于1。

是自动机状态的个数。 

表示在开始时自动机处于第

个状态的概率。包含有不可靠元件的数字电路和通信的信道都可以表示为概率自动机。

发展简况  早在40年代末，C.E.仙农在信息论的研究中，就提出了噪声信道的数学模型(见图[噪声信道]

)，它实际上就是一种概率自动机。50年代初，J.诺伊曼研究用不可靠元件构造可靠机器，这个问题发展成为现代的容错计算问题。但是直到50年代末，在R.W.阿西贝的著作中才给出一个形式定义的雏形。1963年M.O.拉宾比较严格地阐述了概率自动机的一些基本概念，并提出一些问题(如稳定性问题)。后来，A.帕兹等人的著作综述了这一方面的研究成果。60年代末至70年代，有更多的人进行了这方面的研究工作。

主要内容  与一般的自动机理论相平行的，有概率图灵机、概率时序机、概率识别器等方面的研究工作。这些工作一方面是推广自动机已有的结果;另一方面也提出不少新的问题，丰富了自动机论的内容。

概率图灵机  概率图灵机是图灵机的推广。它的形式定义可以用六元组

=(

,

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