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

  • Article
  • | |
  • Metrics
  • |
  • Reference [7]
  • |
  • Related [20]
  • | | |
  • Comments
    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.

    Reference
    [1] E.一E.Doberkat,Stochastic Automata; Stability,Nondeterminism and Prediction,Lecture Notes in ComDuter Sci. ence 113,Springer-Verlag,Berlin,1981.
    [2] J.T.Gill,Computational Complexity of Probabilistic Turing Machines,SIAM.J.Comput.6,1977,675-695.
    [3] M.O.Rabin Probabilistic Automata,Information.and Control 6,1963,230-245.
    [4] E.S.Santos,Probabilistic Turing Machines and Computability Proc.Amer.Math.Soc.22,1969,704-710.
    [5] E.S.Santos,Computability by Probabilistic Turing Machines,Trans.Amer.Math.Soc.4,1971,165-184.
    [6] J.C.Shepherdson and H.E.Sturgis,Computability of Recursive Functions.J.Assoc.Comput.Mach.10,1963,217—255.
    [7] D.J.A.Welsh,Randomized Algorithms,Discrete Appl.Math.5,1983.133-146.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:4668
  • PDF: 4963
  • HTML: 0
  • Cited by: 0
History
  • Received:January 07,1990
  • Revised:November 15,1990
You are the first2032791Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063