I’m a physics and math student working through Nielsen & Chuang’s text on quantum computation and information. I don’t have much experience in CS theory, so some of these exercises are confusing to me:
Suppose we number the probabilistic Turing machines and define the probabilistic halting function $ h_p(x)$ to be 1 if machine $ x$ halts on input of $ x$ with probability at least 1/2 and 0 if machine $ x$ halts on input of $ x$ with probability less than 1/2. Show that there is no probabilistic Turing machine which can output $ h_p(x)$ with probability of correctness strictly greater than 1/2 for all $ x$ .
I’m sure we’re supposed to assume that there is a probabilistic Turing machine that does this, and then show that we can solve the deterministic halting problem using this machine, thus obtaining a contradiction. I don’t have a clue how to go from this probabilistic Turing machine to a deterministic one, though.