Real number $p$ such that a $p$-coin makes the undecidable decidable This is an exercice from Arora &amp; 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.
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 &lt; 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 &lt; 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) &amp; \text{if } f(i) \in H \\
    (0, 1) &amp; \text{if } f(i) \not\in H.
  \end{cases}
$$

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


If $x$ is not of the form $1^{4^k}$ for some $k \in \mathbb{N}$, reject. Otherwise, compute $k$.
Flip the coin $t = \lceil 3\cdot4^{2k+2}\ln(6)) \rceil$ times, counting the number of heads $s$.
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 &lt; 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 &lt; 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] 
  &amp;\leq 2\exp\left(-\frac{t}{3 \cdot 4^{2k+2} p}\right) \\
  &amp;\leq 2\exp\left(-\frac{3\cdot4^{2k+2}\ln(6)}{3 \cdot 4^{2k+2} p}\right) \\
  &amp;= 2\exp\left(-\ln(6)/p\right) \\
  &amp;&lt; 2\exp\left(-\ln(6)\right) \\
  &amp;= 1/3.
\end{align*}
$$
Thus $\operatorname{Pr}\left[\lvert s/t - p \rvert &lt; 2^{-2k-2}\right] &gt; 2/3$, so our algorithm is correct with probability at least $2/3$.