Real number $p$ such that a $p$-coin makes the undecidable decidable
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$.