# How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time? [closed]

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.

• Somehow I think I should use Chernoff bound but I don't know how. – Hope May 6 '19 at 1:56
• We don’t do homework problems here. Look up Chaitin’s constant. – Aryeh May 6 '19 at 4:28
• 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 May 6 '19 at 13:50
• OK, there's a minor trick -- see my answer below. – Aryeh May 6 '19 at 15:01

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.

• 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 May 7 '19 at 4:17
• 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 May 7 '19 at 4:42
• 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 amazon.com/… – Aryeh May 7 '19 at 7:13
• 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 May 8 '19 at 7:49
• Indeed— though one does need to make the encoding of the language “exponentially inefficient”, I think. – Aryeh May 8 '19 at 7:59