6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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, 2013 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, 2013 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, 2013 at 6:29

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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, 2013 at 10:51
  • 2
    $\begingroup$ That sounds right. $\endgroup$
    – Peter Shor
    Nov 12, 2013 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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