<p>If you have a coin which has an uncomputable probability of landing heads, then you can estimate with bounded error the first $k$ bits of this probability using $O(4^{k})$ coin flips. </p>

<p>This lets you construct a machine with bounded error that computes an uncomputable function. The uncomputable function is the $k$<sup>th</sup> bit of the probability. The computation is estimating the probability of landing heads by flipping the coin $4^k$ times. Considerations of running time don't matter when you're worrying about whether a function is computable or uncomputable, so it doesn't matter that it takes time exponential in $k$ to estimate the $k$<sup>th</sup> bit of the function; it's still an uncomputable function.</p>

CC BY-SA 3.0
2013-11-12T10:51:10.077Z
So, for any given unary language, say $ L $, there is a probability $ 0.x $ such that $ x(i) $ is 1 (resp. 6) if $ a^i $ is not in $ L $ (resp. is in $ L $). Thus, unary language $\{ a^{4^k} \mid k \in L \}$ can be recognized by a log-space bounded-error PTM having a coin which has $0.x$ probability of landing heads. Am I missing something?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-11-12T11:50:04.800Z
That sounds right.
Peter Shor 
CC BY-SA 3.0
2013-11-11T11:48:22.027Z
2013-11-12T06:23:21.700Z
2013-11-12T06:23:21.700Z
Peter Shor 
<p>In the unbounded-error case, it is known that both realtime quantum and probabilistic finite automata can recognize some uncomputable languages if they are allowed to use arbitrary real numbers in their transitions (<a href="http://www.sciencedirect.com/science/article/pii/S0019995863902900" rel="nofollow">Rabin, 1963</a>; <a href="http://www.sciencedirect.com/science/article/pii/S0890540111000319" rel="nofollow">Yakaryilmaz and Say, 2011</a>).</p>

<p>In the bounded-error case, we have a similar result for poly-time quantum Turing machines as well, i.e. the cardinality of $ \mathsf{BQP}_{\mathbb{C}}  $ is uncountable (<a href="http://epubs.siam.org/doi/abs/10.1137/S0097539795293639" rel="nofollow">Adleman et. al., 1997</a>). </p>

<p>My question is whether any <strong>bounded-error probabilistic</strong> space (time) class defined with unrestricted real numbers contains an uncomputable (or a recursive enumerable) language.</p>

<p>It is also known that (<a href="http://link.springer.com/article/10.1007/s00037-003-0177-8" rel="nofollow">Watrous, 2003</a>) if we restrict ourselves to algebraic numbers ($\mathbb{A}$), for any space-constructable function $ s(n) \in \Omega(\log n) $, 
\begin{equation}
\mathsf{PrQSPACE}_{\mathbb{A}}(s) \subseteq \mathsf{DSPACE}(s^2),
\end{equation}
where $\mathsf{PrQSPACE}$ stand for unbounded-error quantum space.</p>

<p>Any partial answer (for the case of <strong>bounded-error probabilistic</strong> computation using non-algebraic transitions) violating this upper bound would also be nice.</p>

CC BY-SA 3.0
2013-11-12T05:18:55.960Z
I don't understand your question. Are you interested in space or time classes? For time, Yamakami and Yao (http://arxiv.org/abs/quant-ph/9812032) showed that unrestricted complex numbers do not affect the power of NQP.
Marcos Villagra
CC BY-SA 3.0
2013-11-12T06:29:06.263Z
@Marcos: that's a result about NQP, not about BQP. The OP is asking about BPP, which like BQP contains uncountable languages if the probabilities can be uncomputable numbers.
Peter Shor 
CC BY-SA 3.0
2013-11-12T06:29:59.343Z
@Peter: yes, that is correct. That's why I don't know what is Abuzer looking for. The question doesn't say if it is only about polynomial time computation.
Marcos Villagra
<reference-request><probabilistic-computation><quantum-computing>
Is bounded-error probabilistic computation sensitive to transition types?
Abuzer Yakaryilmaz
# Is bounded-error probabilistic computation sensitive to transition types?

(Asked by: username_0 on 2013-11-06)

In the unbounded-error case, it is known that both realtime quantum and probabilistic finite automata can recognize some uncomputable languages if they are allowed to use arbitrary real numbers in their transitions ([Rabin, 1963](http://www.sciencedirect.com/science/article/pii/S0019995863902900); [Yakaryilmaz and Say, 2011](http://www.sciencedirect.com/science/article/pii/S0890540111000319)).

In the bounded-error case, we have a similar result for poly-time quantum Turing machines as well, i.e. the cardinality of $ \mathsf{BQP}\_{\mathbb{C}} $ is uncountable ([Adleman et. al., 1997](http://epubs.siam.org/doi/abs/10.1137/S0097539795293639)).

My question is whether any **bounded-error probabilistic** space (time) class defined with unrestricted real numbers contains an uncomputable (or a recursive enumerable) language.

It is also known that ([Watrous, 2003](http://link.springer.com/article/10.1007/s00037-003-0177-8)) if we restrict ourselves to algebraic numbers ($\mathbb{A}$), for any space-constructable function $ s(n) \in \Omega(\log n) $,
\begin{equation}
\mathsf{PrQSPACE}\_{\mathbb{A}}(s) \subseteq \mathsf{DSPACE}(s^2),
\end{equation}
where $\mathsf{PrQSPACE}$ stand for unbounded-error quantum space.

Any partial answer (for the case of **bounded-error probabilistic** computation using non-algebraic transitions) violating this upper bound would also be nice.

**Tags:** reference-request, probabilistic-computation, quantum-computing
> **Comments:**
> **username_1**: I don't understand your question. Are you interested in space or time classes? For time, Yamakami and Yao (http://arxiv.org/abs/quant-ph/9812032) showed that unrestricted complex numbers do not affect the power of NQP.  
> **username_2**: @Marcos: that's a result about NQP, not about BQP. The OP is asking about BPP, which like BQP contains uncountable languages if the probabilities can be uncomputable numbers.  
> **username_1**: @Peter: yes, that is correct. That's why I don't know what is Abuzer looking for. The question doesn't say if it is only about polynomial time computation.  

---

## 1 answers

### Answer by username_2 on 2013-11-11. Score: 10 | Accepted answer

If you have a coin which has an uncomputable probability of landing heads, then you can estimate with bounded error the first $k$ bits of this probability using $O(4^{k})$ coin flips.

This lets you construct a machine with bounded error that computes an uncomputable function. The uncomputable function is the $k$th bit of the probability. The computation is estimating the probability of landing heads by flipping the coin $4^k$ times. Considerations of running time don't matter when you're worrying about whether a function is computable or uncomputable, so it doesn't matter that it takes time exponential in $k$ to estimate the $k$th bit of the function; it's still an uncomputable function.

> **Comments:**
> **username_0**: So, for any given unary language, say $ L $, there is a probability $ 0.x $ such that $ x(i) $ is 1 (resp. 6) if $ a^i $ is not in $ L $ (resp. is in $ L $). Thus, unary language $\{ a^{4^k} \mid k \in L \}$ can be recognized by a log-space bounded-error PTM having a coin which has $0.x$ probability of landing heads. Am I missing something?  
> **username_2**: That sounds right.  

---

