2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Have you tried diagonalization? $\endgroup$ – Yuval Filmus Jul 23 at 3:27
  • $\begingroup$ A word of warning. I tried to work through Nielsen and Chuang when I was a grad student. I found their description of quantum mechanics seriously hard going so, out of curiosity, I went back and looked at their chapter on computability theory for physicists. I found I could hardly understand their presentation of that material, even though I was teaching computability to undergraduates at the time. You might want to try another book. Sipser is very good for Turing machines. $\endgroup$ – David Richerby Jul 23 at 12:20
  • $\begingroup$ This section had me confused a few times, mainly with the concept of algorithms as Turing machines, but also as programs we can run on Turing machines. The previous exercise to this was the blank tape halting problem, which I now understand, but when I was first working with it I wasn't sure how we could just construct an algorithm that took a Turing machine itself as input. I guess I just have to not worry about the "level" of abstractness I'm working with. $\endgroup$ – Rourke Sekelsky Jul 23 at 15:24
2
$\begingroup$

Let $A$ be a randomized procedure which outputs $h_p$ with success probability larger than $1/2$.

Consider the following code, with input $x$:

  • Let $y$ be the machine corresponding to machine $x$ running on itself as input.
  • If $A(y) = 1$, go into an infinite loop, otherwise halt.

Denote this program by $B$. What happens if we run $B$ on itself? Let us consider two cases. In both cases, let $y$ be the machine corresponding to $B$ running on itself.

Case 1: $B$ halts on $B$ with probability at least $1/2$. In this case, $h_p(y) = 1$, and so with probability more than $1/2$, $A(y) = 1$. Therefore $B$ goes into an infinite loop with probability more than $1/2$, contradiction.

Case 2: $B$ halts on $B$ with probability smaller than $1/2$. In this case, $h_p(y) = 0$, and so with probability more than $1/2$, $A(y) = 0$. Therefore $B$ halts with probability more than $1/2$, contradiction.

(This generalizes the usual proof of uncomputability of the halting problem via diagonalization.)

$\endgroup$
  • $\begingroup$ Great answer, I'll try to use this idea in the future. I expected to have to use probabilistic machines to solve the halting problem on deterministic machines, but thinking about this earlier I figured they couldn't be connected well (at least with what material the authors have provided so far). Thanks! $\endgroup$ – Rourke Sekelsky Jul 23 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.