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; Yakaryilmaz and Say, 2011).

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).

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) 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.

  • $\begingroup$ I don't understand your question. Are you interested in space or time classes? For time, Yamakami and Yao (arxiv.org/abs/quant-ph/9812032) showed that unrestricted complex numbers do not affect the power of NQP. $\endgroup$ – Marcos Villagra Nov 12 '13 at 5:18
  • $\begingroup$ @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. $\endgroup$ – Peter Shor Nov 12 '13 at 6:29
  • $\begingroup$ @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. $\endgroup$ – Marcos Villagra Nov 12 '13 at 6:29

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.

  • 2
    $\begingroup$ 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? $\endgroup$ – Abuzer Yakaryilmaz Nov 12 '13 at 10:51
  • 2
    $\begingroup$ That sounds right. $\endgroup$ – Peter Shor Nov 12 '13 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.