home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2792 < prev    next >
Encoding:
Internet Message Format  |  1993-01-05  |  1.7 KB
  1. Path: sparky!uunet!pipex!bnr.co.uk!uknet!pavo.csi.cam.ac.uk!nmm1
  2. From: nmm1@cus.cam.ac.uk (Nick Maclaren)
  3. Newsgroups: comp.theory
  4. Subject: Probabilistic Turing Machines
  5. Message-ID: <1993Jan5.191925.27528@infodev.cam.ac.uk>
  6. Date: 5 Jan 93 19:19:25 GMT
  7. Sender: news@infodev.cam.ac.uk (USENET news)
  8. Organization: U of Cambridge, England
  9. Lines: 34
  10. Nntp-Posting-Host: bootes.cus.cam.ac.uk
  11.  
  12.  
  13. Consider standard deterministic Turing machines with a fixed, finite program
  14. and an arbitrary input tape (i.e. the input is deemed separate from the
  15. program.  Consider probabilistic versions with the program extended to
  16. allow the generation of a true random bit.
  17.  
  18. Clearly the second model is strictly more powerful than the first, but I
  19. am interested (for now) only in deterministic problems - that is ones
  20. where the output and termination (if any) depend solely on the input tape.
  21.  
  22. 1) Is it known whether there are any deterministic problems that can be
  23. solved by probabilistic Turing machines but not by deterministic ones?
  24.  
  25. 2) Is it known that there are no such algorithms?
  26.  
  27. 3) Assuming (2), are there any deterministic problems that have a lower
  28. complexity for probabilistic Turing machines than deterministic ones?
  29.  
  30. 4) Is is known that there are no such problems?
  31.  
  32. Does anyone know of any good results/references on these questions?
  33. Please note that I am NOT working in the automata area, but am interested
  34. because they affect the theoretical justification for pseudorandom
  35. numbers.  I know that there are zillions of probabilistic algorithms,
  36. many of which predate Turing, but that isn't much help!
  37.  
  38.  
  39. Nick Maclaren
  40. University of Cambridge Computer Laboratory,
  41. New Museums Site, Pembroke Street,
  42. Cambridge CB2 3QG, England.
  43. Email:  nmm1@cus.cam.ac.uk
  44. Tel.:   +44 223 334761
  45. Fax:    +44 223 334679
  46.