patternMinor
Why is a deterministic Turing machine a special case of a probabilistic Turing machine?
Viewed 0 times
casewhyprobabilisticspecialdeterministicmachineturing
Problem
I have no formal training in computer science as I have not yet taken any such classes, so perhaps this question appears naive. I was reading about BPP and it was claimed that a deterministic Turing machine is a special case of a probabilistic Turing machine. I don't understand why this is.
Solution
Probabilistic Turing machines are similar to deterministic Turing machines, but have the additional power of tossing coins. If you never make use of this power, you get a deterministic Turing machine.
In a similar fashion, a non-deterministic Turing machine is allowed to make guesses, but if it doesn't it is just a deterministic Turing machine.
In a similar fashion, a non-deterministic Turing machine is allowed to make guesses, but if it doesn't it is just a deterministic Turing machine.
Context
StackExchange Computer Science Q#47918, answer score: 6
Revisions (0)
No revisions yet.