HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is a deterministic Turing machine a special case of a probabilistic Turing machine?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#47918, answer score: 6

Revisions (0)

No revisions yet.