关于概率无限寄存器机器PURM及其程序可模拟的随机函数
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


THE PROBABILISTIC UNLIMITED REGISTER MACHINE (PURM) AND THE RANDOM FUNCTIONS THAT CAN BE SIMULATED BY PURM PROGRAMS
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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.

    参考文献
    相似文献
    引证文献
引用本文

党哲,周维芳.关于概率无限寄存器机器PURM及其程序可模拟的随机函数.软件学报,1992,3(4):12-18

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1990-01-07
  • 最后修改日期:1990-11-15
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号