Talk:Probabilistic Turing machine

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]

The difference between a probabilistic Turing machine and a deterministic one has to do with how their transition tables are defined. So for a DTM, if the input on the tape is 'a', it erases it and writes 'b' on the tape. For a probabalistic machine, if the input is 'a' 50% of the time it writes 'b' and 50% of the time it writes 'c'. You can obviously approximate this with two deterministic TM's, creating a composite deterministic machine that can do everything that the non-deterministic machine does. The question is whether you can always transform a probabalistic TM into a collection of deterministic TM's by replacing probabalistic transitions with n outputs with f(n) deterministic Turing machines. That's where the polynomial space/time consideration comes in- can you create a probabalistic Turing machine where the number of DTM's needed to simulate requires more than a polynomial number of Turing machines.

From a computational perspective, it doesn't matter if the source of randomness for the probabalistic machine is 'true' randomness or psuedo-randomness- a randomness source is something like a 'peripheral' or oracle that communicates with a TM (deterministic or not). So there is more to a probabalistic TM than just a TM with a randomness source- you could theoretically create a Turing machine where location 'x' on the tape always contained the output of a random oracle. That expands the definition of a TM a little bit, but is still not equivalent to a probabalistic machine. Polynomial time/space has to do with how much time/space you need to simulate a non-deterministic transition with n outputs using n deterministic Turing machines.

Finally, 'power' in computational theory is defined in terms of equivalence classes of problems that the machine can solve. If you need an exponential time transformation to solve problem x on machine y, a machine that decides problem x in polynomial time is more powerful than machine y. Random vs. psuedo-random just has to do with the use of an external oracle to provide a randomness source (similar to a peripheral on a real computer) so even if you can make a random number generator from a machine with an oracle, the fact that you can't do so with a machine without an oracle doesn't mean that one machine is more powerful than the other- the apparent 'power' comes not from mathematical expressiveness or computation capacity, but from the addition of the external oracle. A probabalistic TM requires an external oracle in order for its transition function to work, whereas a ordinary TM does not, but 'power' refers to the problems that the resulting machine can solve, not the presence or absence of an oracle. --Spasemunki (talk) 22:04, 19 January 2017 (UTC)[reply]