摘要
本文给出了一种新的随机计算的机器模型:概率无限寄存器机器PURM,它比概率Turing机(PTM)更为简单。我们证明了PURM程序与可计算的PTM之间的等价性。基于对PURM程序的构造,我们给出了随机函数可被PURM程序或可计算的PTM模拟的充分条件。最后,讨论了PTM和PURM的一些简单性质。
In this paper, a new model for randomized computation-the Probabilistic
Unlimited Register Machine(PURM) which is simpler than the Probabilistic Turing Machine (PTM)[4,5] is given. We prove the equivalence between PURM program and computable PTM. Moreover, by constructing the PURM programs, we get the sufficiant conditions for a random function that can be simulated by PURM program or PTM. At last, some simple properties of PTM and PURM are discussed.
出处
《软件学报》
EI
CSCD
北大核心
1992年第4期12-18,共7页
Journal of Software
