Talk:Probabilistic Turing machine

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Merge?

Should random Turing machine be merged with this page? Deco 22:38, 28 Apr 2005 (UTC)

Random Turing machine redirects here... so I guess that'd be a 'yes'. --Ihope127 21:56, 11 July 2005 (UTC)[reply]

old version of Random Turing Machine has some information not in this article. Both are lacking in any citations. It's an important subject so not suggesting the content is removed but citations would be good. Robert Walker (talk) 07:15, 5 August 2016 (UTC)[reply]

Confused

I am confused by "One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem which can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine?"

A probabilistic Turing machine can (I imagine) print out a series of random numbers. A Turing machine cannot - it can only print out pseudorandom numbers which are demonstrably different. So isn't this question (above) trivial?

Perhaps a probabilistic Turing machine cannot do this. If so a randomised Turing machine (one with a quantum or other kind of true random number generator) certainly can. Polynomial time is certainly not the issue here. In which case "random Turing machine" probably should not redirect here as it is then a different entity. Keithbowden (talk) 13:09, 19 January 2017 (UTC)[reply]