关于概率无限寄存器机器purm及其程序可模拟的随机函数

本文给出了一种新的随机计算的机器模型:概率无限寄存器机器purm,它比概率turing机(ptm)更为简单。我们证明了purm程序与可计算的ptm之间的等价性。基于对purm程序的构造,我们给出了随机函数可被purm程序或可计算的ptm模拟的充分条件。最后,讨论了ptm和purm的一些简单性质。