# Turing Machine

Let B be a probabilistic polynomial time Turing machine and let C be a language where, for some fixed 0 < 1 < 2 < 1,

a. w  C implies Pr [B accepts w]  1, and

b. w  C implies Pr [B accepts w]  2.

Show that C  BPP. HINT:

Use Lemma 10.5 to help you find the solution.

See attached file for full problem description.

© BrainMass Inc. brainmass.com June 3, 2020, 1:37 pm ad1c9bdddfhttps://brainmass.com/computer-science/theoretical-computer-science/turing-machine-probabilities-120807

#### Solution Preview

The basic idea is to reach at a stage where we can use the lemma 10.5. That is we need to reduce the error probability. A most useful tool in this is is the Chernoff bound. Chernoff bound is used to ...

#### Solution Summary

Turing Machine inquiry is presented.

$2.19