<p>I'll take as given the existence of Chaitin's constant <span class="math-container">$\Omega\in[0,1]$</span>, and that knowing its first <span class="math-container">$k$</span> bits is equivalent to be able to decide the halting problem for all Turning machines of size up to <span class="math-container">$k$</span>:
<a href="https://en.wikipedia.org/wiki/Chaitin%27s_constant" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Chaitin%27s_constant</a></p>

<p>Given access to an <span class="math-container">$\Omega$</span>-biased coin, one can use Chernoff bounds to compute <span class="math-container">$\hat\Omega_k$</span>, which agrees with <span class="math-container">$\Omega$</span> up to <span class="math-container">$k$</span> bits (i.e., <span class="math-container">$|\Omega-\hat\Omega_k|&lt;1/2^{k+1}$</span>), by sampling the coin <span class="math-container">$O(2^{2k})$</span> times. Now this is exponential in <span class="math-container">$k$</span> and is actually tight, so how does this square with the problem statement:
"Describe a real number <span class="math-container">$\rho$</span> such that given a random coin that comes up “Heads” with probability <span class="math-container">$\rho$</span>, a Turing machine can decide <b>an</b> undecidable language in <em>polynomial</em> time" ?</p>

<p>The trick is to use a very inefficient encoding for the undecidable language.
Fix a universal encoding (the same one used to define <span class="math-container">$\Omega$</span>) and consider the language <span class="math-container">$L$</span>, which consists of all Turing machine descriptions <span class="math-container">$&lt;M&gt;$</span>, such that <span class="math-container">$M$</span> halts on all inputs. Clearly, <span class="math-container">$L$</span> is undecidable. Now order <span class="math-container">$L$</span> in lexicographic order where <span class="math-container">$&lt;M_i&gt;$</span> is the <span class="math-container">$i$</span>th word, and define <span class="math-container">$L'$</span> to consist of the words <span class="math-container">$&lt;M_i'&gt;$</span>, where <span class="math-container">$M_i'$</span> is a TM equivalent to <span class="math-container">$M_i$</span> (the two halt on and accept the same set of inputs), but <span class="math-container">$M_i'$</span> contains an additional <span class="math-container">$2^i$</span> dummy states.</p>

<p>Thus, to determine whether a word <span class="math-container">$x$</span> belongs to the undecidable language <span class="math-container">$L'$</span>, one only needs to know <span class="math-container">$O(\log|x|)$</span> bits of <span class="math-container">$\Omega$</span>, which is feasible in expected poly<span class="math-container">$(|x|)$</span> time via the argument above.</p>

CC BY-SA 4.0
2019-05-07T04:17:06.130Z
Thanks, Aryeh! I still have a little problem understanding it but your logic seems right. I just want to add Chaitin's constant is a real number that is not computable.
Hope
CC BY-SA 4.0
2019-05-07T04:42:17.627Z
One more question, the book didn't mention Chaitin's constant at all and I didn't heard of that before. It seems without knowing of Chaitin's constant it is impossible to do the prove. Where should I learn this? Can you please introduce a good reference that can be more helpful?
Hope
CC BY-SA 4.0
2019-05-07T07:13:36.563Z
That's a good pedagogical question. Maybe the author expects you to discover something like $\Omega$ on your own. For background on the latter, you can look here
https://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954
Aryeh
CC BY-SA 4.0
2019-05-08T07:49:00.247Z
You just need to come up with the idea to encode the HALTING language as an infinite string. I don't think that's unreasonable.
Sasho Nikolov
CC BY-SA 4.0
2019-05-08T07:59:26.563Z
Indeed— though one does need to make the encoding *of the language* “exponentially inefficient”, I think.
Aryeh
CC BY-SA 4.0
2019-05-11T23:45:53.670Z
Sasha, can you please explain more?
Hope
CC BY-SA 4.0
2019-05-06T15:00:36.320Z
2019-05-06T15:00:36.320Z
Aryeh
<p>In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm a new power. Then he  states: "The exercises show that if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power."</p>

<p>Lemma 7.12: A coin with Pr[Heads] = ρ can be simulated by a PTM in expected time O(1) provided the ith bit of ρ is computable in poly(i) time.</p>

<p>The exercise that supposed to show, if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power is the following:</p>

<p>Exercise: Describe a real number ρ such that given a random coin that comes up “Heads” with probability ρ, a Turing machine can decide an undecidable language in polynomial time. </p>

<p>Now, how can we show that if ρ is not efficiently computable, then a ρ-coin can indeed provide an additional power for a probabilistic algorithm to decide some undeniable language in polynomial time?</p>

<p>*I removed the hint because it made me more confused but you can find it at the end of the book.</p>

<p>I strongly believe that this is a research level problem and proper to be discussed in theoretical computer science society because this is a high level question about computational complexity and this question has not been discussed anywhere else. </p>

CC BY-SA 4.0
2019-05-06T01:56:46.567Z
Somehow I think I should use Chernoff bound but I don't know how.
Hope
CC BY-SA 4.0
2019-05-06T04:28:34.653Z
We don’t do homework problems here. Look up Chaitin’s constant.
Aryeh
CC BY-SA 4.0
2019-05-06T13:50:14.383Z
Aryeh, I checked Chaitin’s constant it seems it is not efficiently computable but how can it provide an additional power for probabilistic algorithm?
Hope
CC BY-SA 4.0
2019-05-06T15:01:19.450Z
OK, there's a minor trick -- see my answer below.
Aryeh
<cc.complexity-theory><randomized-algorithms><randomness><chernoff-bound>
How to use a -coin so a TM can decide an undecidable language in polynomial time?
Hope
# How to use a -coin so a TM can decide an undecidable language in polynomial time?

(Asked by: username_0 on 2019-05-06)

In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm a new power. Then he states: "The exercises show that if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power."

Lemma 7.12: A coin with Pr[Heads] = ρ can be simulated by a PTM in expected time O(1) provided the ith bit of ρ is computable in poly(i) time.

The exercise that supposed to show, if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power is the following:

Exercise: Describe a real number ρ such that given a random coin that comes up “Heads” with probability ρ, a Turing machine can decide an undecidable language in polynomial time.

Now, how can we show that if ρ is not efficiently computable, then a ρ-coin can indeed provide an additional power for a probabilistic algorithm to decide some undeniable language in polynomial time?

\*I removed the hint because it made me more confused but you can find it at the end of the book.

I strongly believe that this is a research level problem and proper to be discussed in theoretical computer science society because this is a high level question about computational complexity and this question has not been discussed anywhere else.

**Tags:** cc.complexity-theory, randomized-algorithms, randomness, chernoff-bound

> **Comments:**
> **username_0**: Somehow I think I should use Chernoff bound but I don't know how.  
> **username_1**: We don’t do homework problems here. Look up Chaitin’s constant.  
> **username_0**: username_1, I checked Chaitin’s constant it seems it is not efficiently computable but how can it provide an additional power for probabilistic algorithm?  
> **username_1**: OK, there's a minor trick -- see my answer below.  

---

## 1 answers

### Answer by username_1 on 2019-05-06. Score: 4

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up to $k$:
<https://en.wikipedia.org/wiki/Chaitin%27s_constant>

Given access to an $\Omega$-biased coin, one can use Chernoff bounds to compute $\hat\Omega\_k$, which agrees with $\Omega$ up to $k$ bits (i.e., $|\Omega-\hat\Omega\_k|<1/2^{k+1}$), by sampling the coin $O(2^{2k})$ times. Now this is exponential in $k$ and is actually tight, so how does this square with the problem statement:
"Describe a real number $\rho$ such that given a random coin that comes up “Heads” with probability $\rho$, a Turing machine can decide **an** undecidable language in *polynomial* time" ?

The trick is to use a very inefficient encoding for the undecidable language.
Fix a universal encoding (the same one used to define $\Omega$) and consider the language $L$, which consists of all Turing machine descriptions $$, such that $M$ halts on all inputs. Clearly, $L$ is undecidable. Now order $L$ in lexicographic order where $$ is the $i$th word, and define $L'$ to consist of the words $$, where $M\_i'$ is a TM equivalent to $M\_i$ (the two halt on and accept the same set of inputs), but $M\_i'$ contains an additional $2^i$ dummy states.

Thus, to determine whether a word $x$ belongs to the undecidable language $L'$, one only needs to know $O(\log|x|)$ bits of $\Omega$, which is feasible in expected poly$(|x|)$ time via the argument above.

> **Comments:**
> **username_0**: Thanks, username_1! I still have a little problem understanding it but your logic seems right. I just want to add Chaitin's constant is a real number that is not computable.  
> **username_0**: One more question, the book didn't mention Chaitin's constant at all and I didn't heard of that before. It seems without knowing of Chaitin's constant it is impossible to do the prove. Where should I learn this? Can you please introduce a good reference that can be more helpful?  
> **username_1**: That's a good pedagogical question. Maybe the author expects you to discover something like $\Omega$ on your own. For background on the latter, you can look here https://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954  
> **username_2**: You just need to come up with the idea to encode the HALTING language as an infinite string. I don't think that's unreasonable.  
> **username_1**: Indeed— though one does need to make the encoding *of the language* “exponentially inefficient”, I think.  
> **username_0**: Sasha, can you please explain more?  

---

