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

学习可以这样来看，它是一个潜移默化、厚积薄发的过程。www.xiaozhibei.com编辑了数学百科知识专题：概率自动机论，希望对您有所帮助!

 自动机论的次级学科，主要研究所处环境或内部具有（有限或无限的）随机因素的自动机。与非概率型自动机不同之处，是概率自动机的动作是随机的。为了给定概率自动机,首先必需规定在自动机处于某一状态,并向自动机输入某个字母的条件下，自动机下一动作（如状态转移，输出某个字母，改写字母等）的条件概率函数。其次是给定自动机的初始状态的概率分布──初始分布，一般用一个随机矢量＝(，，…，)表示，其中各个都是非负的，且相加之和等于1。是自动机状态的个数。 表示在开始时自动机处于第个状态的概率。包含有不可靠元件的数字电路和通信的信道都可以表示为概率自动机。

   发展简况  早在40年代末，C.E.仙农在信息论的研究中，就提出了噪声信道的数学模型(见图[噪声信道])，它实际上就是一种概率自动机。50年代初，J.诺伊曼研究用不可靠元件构造可靠机器，这个问题发展成为现代的容错计算问题。但是直到50年代末，在R.W.阿西贝的著作中才给出一个形式定义的雏形。1963年M.O.拉宾比较严格地阐述了概率自动机的一些基本概念，并提出一些问题（如稳定性问题）。后来，A.帕兹等人的著作综述了这一方面的研究成果。60年代末至70年代，有更多的人进行了这方面的研究工作。
   主要内容  与一般的自动机理论相平行的，有概率图灵机、概率时序机、概率识别器等方面的研究工作。这些工作一方面是推广自动机已有的结果；另一方面也提出不少新的问题，丰富了自动机论的内容。
   概率图灵机  概率图灵机是图灵机的推广。它的形式定义可以用六元组=(,,,,,)给出。其中和分别是非空有限的状态集合和带字母集合。和

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