3
$\begingroup$

Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a classical TM do, but what about the converse?

One can argue that the classical TM will always generate the same result given the same input, while the TM with randomness can behave randomly, it can do more. But, then random-valued functions are not really what we call computable. I am aware of randomized algorithms and BPP and what not, but is there an extension of computability that deals with these kind of questions?

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ You answered the complexity question for yourself (BPP captures efficient probabilistic algorithms). As for computability, it's easy to see that a classical TM can simulate a probabilistic TM given an exponential blow-up in runtime. Intuitively, if a probabilistic TM uses n random bits, then a classical TM can try all $2^n$ paths corresponding to the possible random bit sequences. So, probabilistic TMs cannot decide a larger class of functions than classical TMs. The outstanding question is whether they can compute certain functions faster. $\endgroup$
    – Huck Bennett
    Apr 24 '12 at 18:58
  • 2
    $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$
    – Kaveh
    Apr 24 '12 at 19:03
  • 3
    $\begingroup$ @David: After looking at the links, I'm still not sure that I follow. My concerns are the following: (1) "Almost surely" halting is not the same as halting. It seems that the issue you raise is dependent on a different definition of "computable". (2) Given a probabilistic TM which is guaranteed to halt on every input, meaning that only a finite number of random bits may be used by the probabilistic TM, we can simulate it with a classical TM by trying the algorithm with all bit sequences of length 1,2,... This procedure will halt even if we have no a priori time bound on the probabilistic TM. $\endgroup$
    – Huck Bennett
    Apr 24 '12 at 22:49
  • 3
    $\begingroup$ @Suresh: I do not think that the issue raised by David Harris is at the research level, either. Of course, the model becomes equivalent to RE under a certain definition of “computable,” but that does not make the issue interesting. $\endgroup$
    – Tsuyoshi Ito
    Apr 24 '12 at 22:54
  • 3
    $\begingroup$ I found a related question here cstheory.stackexchange.com/questions/2515/… $\endgroup$
    – Memming
    Apr 25 '12 at 13:34
3
$\begingroup$

See https://mathoverflow.net/questions/58060/can-randomness-add-computability

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ original $\endgroup$
    – Kaveh
    Apr 24 '12 at 19:57
  • $\begingroup$ Thanks. Laurent Bienvenu's second part of the answer (which is quoted in the MO question) is very relevant. $\endgroup$
    – Memming
    Apr 25 '12 at 13:33
-4
$\begingroup$

seems like an active, even central/core area of current research under the heading of "exact power of derandomization". its basically an open question with various open complexity class separations whether randomization adds power, or doesnt. theres also a deep connection to the $\mathsf{P \stackrel{?}{=}NP}$ problem in the natural proofs result of razborov/rudich which shows that, loosely, a $\mathsf{P \neq NP}$ proof would likely allow one to "break" what are now conjectured as "secure" random number generators.

[1] is a broad survey on derandomization literature by Impagliazzo. (think there are other surveys out there but cant find them this moment.) [2] is a rough outline of natural proofs paper. there is also a lot of connection of randomization (via pseudorandom generators) across the semifamous "5 algorithmic worlds" introduced also by Impagliazzo.[3]

basically various complex algorithms have been successfully derandomized in significant advances, but others resist efforts. one famous case study would be the AKS primality algorithm which for decades was a probabilistic test that was cleverly derandomized by AKS & proven to run in P time.

[1] Can every randomized algorithm be derandomized? by Impagliazzo 2006

[2] Natural proofs explained by chris calabro

[3] 2009 workshop on impagliazzos 5 worlds

Improve this answer
$\endgroup$

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.