3
$\begingroup$

This is an exercice from Arora & Barak, Chapter 7 :

Describe a real number $p$ such that given a random coin that comes up "heads" with probability $p$, a Turing machine can decide an undecidable language in polynomial time.

This follows a discussion about the fact that if $p$ is efficiently computable, then it's no better than a $1/2$-coin. But if $p$ can be anything, we get new powers. I guess in this case the way to do is to recover the bits of $p$, but I can't think of a deterministic way to do so.

EDIT : based on comments, this question doesn't seem clear. I'll rephrase it like this, based on my interpretation of 'decide' (if I'm wrong, please let me know):

Describe a real number $p$ such that given a random coin that comes up "heads" with probability $p$, there exists an undecidable language $L$ and a Turing machine $M$ such that $M$ runs in polynomial time, and on input $x$, $M$ outputs $1$ if and only if $x \in L$.

Note that stated like this $M$ makes zero error.

$\endgroup$

closed as off-topic by Kaveh, Jan Johannsen, András Salamon, Sasho Nikolov, Joshua Grochow Jul 13 '16 at 21:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Jan Johannsen, András Salamon, Sasho Nikolov, Joshua Grochow
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ So, don't use a deterministic way. $\;$ $\endgroup$ – user6973 Oct 31 '15 at 16:17
  • 2
    $\begingroup$ You shouldn't be looking for a zero-error algorithm. $\;$ $\endgroup$ – user6973 Oct 31 '15 at 17:08
  • 5
    $\begingroup$ @Ricky: I think you're missing the point here; from the words you're using, one cannot distinguish between the possibility you're ignoring the question the OP actually asked and telling him to do so as well by thinking about something else instead and the possibility you mean to say that "decide" doesn't mean what the OP thinks it means (and, unfortunately, without providing an alternate definition). $\endgroup$ – Hurkyl Nov 1 '15 at 20:20
  • 2
    $\begingroup$ @JWM You are right, it is said that a probabilistic Turing machine (PTM) can decide a language, allowing some error. Based on the comments, I then come to the conclusion that the authors really are looking for a PTM deciding $L$, and not a Turing machine. Thank you everyone! I guess the confusion comes from the usage of 'Turing machine' and not 'PTM' in the question statement, whereas everywhere else in the chapter the distinction is made clear. Anyway, I'll leave the question open in case someone wants to formulate a clear answer, otherwise I'll close it soon. $\endgroup$ – Manuel Lafond Nov 2 '15 at 20:01
  • 2
    $\begingroup$ Well, the statement doesn’t say just “Turing machine”, it says “Turing machine given a random coin that comes up ‘heads’ with probability $p$”. The likely reason they chose this hairy wording instead of “PTM” is that they needed to make explicit that the coin does not have probability 1/2 as in the standard definition. $\endgroup$ – Emil Jeřábek Nov 3 '15 at 12:22
1
$\begingroup$

I was also wondering how to solve this problem. Although the comments seem to suggest that the poster of the question has already solved the problem, I will write up a solution regardless in case anyone else is curious.

Some credit goes to Sidhanth Mohanty. He showed me this question because he was also interested in the solution, and he provided some crucial insights.


As discussed in the comments, we are considering probabilistic Turing machines, so we need only output the correct answer with probability, say, at least $2/3$.

Idea: Let $L$ be some undecidable language. Maybe we can encode the answers in the binary expansion of $p$. Establish a reasonable bijection $f \colon \mathbb{N} \to \{0,1\}^*$ and make the $i$-th bit in the binary expansion $p$ one if $f(i) \in L$ and zero if $f(i) \not\in L$. Now we hope to recover the binary expansion of $p$ by flipping the coin $t$ times, counting the number of heads $s$, and computing $s/t$.

Issue 1: This won't be polynomial time. Given some input $x \in \{0,1\}^*$, the index $f^{-1}(x)$ will be exponential in $|x|$, and determining the $f^{-1}(x)$-th bit of $p$ with high enough probability will take too long.

Fix: We get to choose what $L$ is, so we can make the elements in $L$ large in length.

Issue 2: At first it might seem like in order to determine the $i$-th bit of $p$, it's enough to read off the $i$-th bit of the binary expansion of $s/t$, hoping that $\vert s/t - p \vert < 2^{-i}$. However, this is not enough to guarantee that the $i$-th bit of $s/t$ is equal to the $i$-th bit of $p$. Suppose that $p$ is $0.1_2$ and that you're trying to determine the third bit of $p$. If $s/t$ is less than $p$ by any positive amount, which would occur roughly half the time, the third bit of $s/t$ could be a 1 rather than a 0. 1 Of course, we cannot actually have $p = 0.1_2$ since we’re assuming that $p$ is uncomputable by construction, but if $p$ were close to $0.1_2$ or any other value with a binary expansion that terminates, we would have a similar issue.

Fix: Note that if the $(j+1)$-th bit of $p$ is different from the $(j+2)$-th bit of $p$, then if we have $\vert s/t - p \vert < 2^{-(j+2)}$, the $i$-th bit of $s/t$ is indeed equal to the $i$-th bit of $p$ for all $1 \leq i \leq j$. This suggests that we can fix the issue by redefining $p$ to make lots of adjacent bits different in its binary expansion.

1Also, in this case, you would also have the issue that you couldn't distinguish $0.1_2$ and $0.0\overline{1}_2$.


Clean writeup:

Define $f\colon \mathbb{N} \to \{0, 1\}^*$ with $f(n)$ being $n$ written in binary with the leading $1$ removed. Let $H$ be your favorite undecidable language, e.g. let $$ H = \{x \in \{0,1\}^* : \text{ $x$ describes a Turing machine that halts on the empty string}\}. $$ Then let $L$ be the undecidable language $$ L = \{1^{4^k} : f(k) \in H\}. $$ Denote the binary expansion of $p$ as $0.p_1p_2p_3p_4p_5\ldots$. For every $i \in \mathbb{N}$, we choose $$ (p_{2i-1}, p_{2i}) = \begin{cases} (1, 0) & \text{if } f(i) \in H \\ (0, 1) & \text{if } f(i) \not\in H. \end{cases} $$

Our TM for deciding $L$ does the following on input $x \in \{0,1\}^*$:

  1. If $x$ is not of the form $1^{4^k}$ for some $k \in \mathbb{N}$, reject. Otherwise, compute $k$.
  2. Flip the coin $t = \lceil 3\cdot4^{2k+2}\ln(6)) \rceil$ times, counting the number of heads $s$.
  3. Compute the $(2k-1)$-th bit of the binary expansion of $s/t$. Accept if it is one and reject if it is zero.

The runtime is $O(t) = O\left(\vert x \vert ^ 2 \right)$, which is polynomial time.

To prove correctness, note that $p_{2k-1}$ is one iff $1^{4^k} \in L$. Hence it is enough to prove that the $(2k-1)$-th bit of $s/t$ is equal to $p_{2k-1}$ with probability at least $2/3$. Since $p_{2k+1} \not= p_{2k+2}$, if $\lvert s/t - p \rvert < 2^{-2k-2}$, then for all $i \leq k$ we have that the $i$-th bit of $s/t$ is equal to $p_i$. In particular, if $\lvert s/t - p \rvert < 2^{-2k-2}$, then the algorithm outputs the correct answer.

The Chernoff bound in corollary 5 of this set of notes tells us that for any $\delta \in (0,1)$, we have $$ \operatorname{Pr}\left[\left\vert \frac{s}{t} - p \right\vert \geq \delta p \right] \leq 2\exp\left(-pt\delta^2/3\right). $$ Setting $\delta$ to be $1/(2^{2k+2}p)$, we get $$ \begin{align*} \operatorname{Pr}\left[\left\vert \frac{s}{t} - p \right\vert \geq \frac{1}{2^{2k+2}} \right] &\leq 2\exp\left(-\frac{t}{3 \cdot 4^{2k+2} p}\right) \\ &\leq 2\exp\left(-\frac{3\cdot4^{2k+2}\ln(6)}{3 \cdot 4^{2k+2} p}\right) \\ &= 2\exp\left(-\ln(6)/p\right) \\ &< 2\exp\left(-\ln(6)\right) \\ &= 1/3. \end{align*} $$ Thus $\operatorname{Pr}\left[\lvert s/t - p \rvert < 2^{-2k-2}\right] > 2/3$, so our algorithm is correct with probability at least $2/3$.

$\endgroup$

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