<p>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.</p>

<p>Some credit goes to <a href="https://cstheory.stackexchange.com/users/40339/sidhanth-mohanty">Sidhanth Mohanty</a>. He showed me this question because he was also interested in the solution, and he provided some crucial insights.</p>

<hr>

<p>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$.</p>

<p>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$.</p>

<p>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.</p>

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

<p>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. <sup>1</sup> 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.</p>

<p>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.</p>

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

<hr>

<p>Clean writeup:</p>

<p>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}
$$</p>

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

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

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

<p>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.</p>

<p><a href="http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf" rel="nofollow noreferrer">The Chernoff bound in corollary 5 of this set of notes</a> 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$.</p>

CC BY-SA 3.0
2016-07-12T01:01:22.903Z
2016-07-12T23:02:12.203Z
2017-04-13T12:32:28.080Z
Tom Tseng
<p>This is an exercice from Arora &amp; Barak, Chapter 7 : </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>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):</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>Note that stated like this $M$ makes zero error.</p>

CC BY-SA 3.0
2015-10-31T17:05:37.953Z
Well, what I really meant is I can conceive ways to recover the bits, or language membership, with "good" probability.  But I can't think of a way to decide the language, that is with zero error.
Manuel Lafond
CC BY-SA 3.0
2015-11-01T02:17:04.147Z
I interpret "deciding a language $L$" as outputting $1$ on input $x$ iff $x \in L$.  Are you saying that if I devise an algorithm that is right about $x \in L$ with probability say $2^{-|x|}$, this answers the question ?  I can probably answer that, but that's not what I thought is 'deciding' (though I'm not sure the authors specify).
Manuel Lafond
CC BY-SA 3.0
2015-11-01T02:33:17.050Z
Yes, sorry I meant probability $1 - 2^{-|x|}$.  But sorry for not getting it.  Say I find a probabilistic algorithm $A$ running in poly-time.  I'm still not sure why the question is answered.  Is it because 'deciding' allows probabilistic machines ?  Or because $A$ implies the existence of a non-probabilitic machine doing the job ?  I know it does, as $A$ can be derandomized, but I may take exponential time, whereas the question requires polynomial time.
Manuel Lafond
CC BY-SA 3.0
2015-11-02T16:07:26.517Z
The way the question is phrased now makes no sense, as the random coin does not figure in the conclusion. The Turing machine $M$ must be randomized with the probability-$p$ coin, and you must allow either a decent probability of error, or (for zero-error computation) the running time to be polynomial only in expectation. Furthermore, as far as I can see, nothing in the ambiguous wording in Arora and Barak implies that “zero error” is the intended interpretation.
Emil Jeřábek
CC BY-SA 3.0
2015-11-02T16:29:19.620Z
In fact, even without any time bounds, it is impossible to compute a non-computable language by a randomized machine with zero error. One can always simulate such a machine deterministically by trying all computation paths in parallel, and outputting the result of the first one that halts.
Emil Jeřábek
CC BY-SA 3.0
2015-11-02T18:50:20.307Z
@ManuelLafond: See definition 7.1 in the book, where Arora and Barak defines exactly what is meant by a probabilistic Turing machine _deciding_ a language.
JWM
CC BY-SA 3.0
2015-11-02T20:01:25.770Z
@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.
Manuel Lafond
CC BY-SA 3.0
2015-11-03T12:22:57.580Z
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.
Emil Jeřábek
CC BY-SA 3.0
2015-11-03T23:59:23.030Z
Since this is relate to lemma 7.12 regarding the simulation of $\rho$-coins by PTMs. An alternative interpretation can be they asking to prove that if we can simulate such a random $\rho$-coin with a PTM for some non-effectively computable $\rho$ that we choose, then there is a Turing machine that can decide an undecidable language.
Josué Tonelli-Cueto
<randomness><undecidability>
Real number $p$ such that a $p$-coin makes the undecidable decidable
Manuel Lafond
# Real number $p$ such that a $p$-coin makes the undecidable decidable

(Asked by: username_0 on 2015-10-31)

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.

**Tags:** randomness, undecidability

> **Comments:**
> **username_0**: Well, what I really meant is I can conceive ways to recover the bits, or language membership, with "good" probability.  But I can't think of a way to decide the language, that is with zero error.  
> **username_0**: I interpret "deciding a language $L$" as outputting $1$ on input $x$ iff $x \in L$.  Are you saying that if I devise an algorithm that is right about $x \in L$ with probability say $2^{-|x|}$, this answers the question ?  I can probably answer that, but that's not what I thought is 'deciding' (though I'm not sure the authors specify).  
> **username_0**: Yes, sorry I meant probability $1 - 2^{-|x|}$.  But sorry for not getting it.  Say I find a probabilistic algorithm $A$ running in poly-time.  I'm still not sure why the question is answered.  Is it because 'deciding' allows probabilistic machines ?  Or because $A$ implies the existence of a non-probabilitic machine doing the job ?  I know it does, as $A$ can be derandomized, but I may take exponential time, whereas the question requires polynomial time.  
> **username_1**: The way the question is phrased now makes no sense, as the random coin does not figure in the conclusion. The Turing machine $M$ must be randomized with the probability-$p$ coin, and you must allow either a decent probability of error, or (for zero-error computation) the running time to be polynomial only in expectation. Furthermore, as far as I can see, nothing in the ambiguous wording in Arora and Barak implies that “zero error” is the intended interpretation.  
> **username_1**: In fact, even without any time bounds, it is impossible to compute a non-computable language by a randomized machine with zero error. One can always simulate such a machine deterministically by trying all computation paths in parallel, and outputting the result of the first one that halts.  
> **username_2**: @ManuelLafond: See definition 7.1 in the book, where Arora and Barak defines exactly what is meant by a probabilistic Turing machine _deciding_ a language.  
> **username_0**: @username_2 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.  
> **username_1**: 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.  
> **username_3**: Since this is relate to lemma 7.12 regarding the simulation of $\rho$-coins by PTMs. An alternative interpretation can be they asking to prove that if we can simulate such a random $\rho$-coin with a PTM for some non-effectively computable $\rho$ that we choose, then there is a Turing machine that can decide an undecidable language.  

---

## 1 answers

### Answer by username_4 on 2016-07-12. Score: 1

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](https://cstheory.stackexchange.com/users/40339/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](http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf) 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$.


---

