| 摘要: |
| 本文给出了一种新的随机计算的机器模型:概率无限寄存器机器PURM,它比概率Turing机(PTM)更为简单。我们证明了PURM程序与可计算的PTM之间的等价性。基于对PURM程序的构造,我们给出了随机函数可被PURM程序或可计算的PTM模拟的充分条件。最后,讨论了PTM和PURM的一些简单性质。 |
| 关键词: |
| DOI： |
| 分类号: |
| 基金项目: |
|
| THE PROBABILISTIC UNLIMITED REGISTER MACHINE (PURM) AND THE RANDOM FUNCTIONS THAT CAN BE SIMULATED BY PURM PROGRAMS |
|
Dang Zhe,Zhou Weifang
|
| Abstract: |
| 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. |
| Key words: |
