<p>See <a href="https://mathoverflow.net/questions/58060/can-randomness-add-computability">https://mathoverflow.net/questions/58060/can-randomness-add-computability</a></p>

CC BY-SA 3.0
2012-04-24T19:57:37.577Z
[original](http://cstheory.stackexchange.com/q/1263/)
Kaveh
CC BY-SA 3.0
2012-04-25T13:33:43.300Z
Thanks. Laurent Bienvenu's second part of the answer (which is quoted in the MO question) is very relevant.
Memming
CC BY-SA 3.0
2012-04-24T19:12:47.613Z
2012-04-24T19:12:47.613Z
2017-04-13T12:57:54.777Z
David Harris
<p>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.</p>

<p>[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]</p>

<p>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 &amp; proven to run in P time.</p>

<p>[1] <a href="http://dl.acm.org/citation.cfm?id=1132571" rel="nofollow">Can every randomized algorithm be derandomized?</a> by Impagliazzo 2006</p>

<p>[2] <a href="http://cseweb.ucsd.edu/~ccalabro/essays/nat_pfs.pdf" rel="nofollow">Natural proofs explained by chris calabro</a></p>

<p>[3] <a href="http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/" rel="nofollow">2009 workshop on impagliazzos 5 worlds</a></p>

CC BY-SA 3.0
2012-04-25T03:49:10.227Z
2012-04-25T04:04:59.893Z
2012-04-25T04:04:59.893Z
vzn
<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2012-04-24T18:58:36.060Z
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.
Huck Bennett
CC BY-SA 3.0
2012-04-24T19:03:30.733Z
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.
Kaveh
CC BY-SA 3.0
2012-04-24T19:03:42.747Z
The question seems more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2012-04-24T19:24:33.073Z
@Huck, you are assuming that there is a uniform computable bound on the number of random bits used. One can imagine situations in which there are computational paths using arbitrarily many bits, and you only have termination with probability one (but not certainty).
David Harris
CC BY-SA 3.0
2012-04-24T21:21:31.243Z
While the original question appears to be off-topic, the issue raised by David isn't
Suresh Venkat
CC BY-SA 3.0
2012-04-24T22:49:19.800Z
@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.
Huck Bennett
CC BY-SA 3.0
2012-04-24T22:54:37.597Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-25T13:34:56.950Z
I found a related question here http://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem
Memming
CC BY-SA 3.0
2012-04-27T23:11:13.073Z
possible duplicate of [Truly random number generator: Turing computable?](http://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable)
Timothy Chow
<computability><turing-machines><randomness>
Is a turing machine with random number generator more powerful?
Memming
# Is a turing machine with random number generator more powerful?

(Asked by: username_0 on 2012-04-24)

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?

**Tags:** computability, turing-machines, randomness
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_2**: The question seems more suitable for [cs.se].  
> **username_3**: @Huck, you are assuming that there is a uniform computable bound on the number of random bits used. One can imagine situations in which there are computational paths using arbitrarily many bits, and you only have termination with probability one (but not certainty).  
> **username_4**: While the original question appears to be off-topic, the issue raised by David isn't  
> **username_1**: @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.  
> **username_5**: @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.  
> **username_0**: I found a related question here http://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem  
> **username_6**: possible duplicate of [Truly random number generator: Turing computable?](http://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable)  

---

## 2 answers

### Answer by username_3 on 2012-04-24. Score: 4 | Accepted answer

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

> **Comments:**
> **username_2**: [original](http://cstheory.stackexchange.com/q/1263/)  
> **username_0**: Thanks. Laurent Bienvenu's second part of the answer (which is quoted in the MO question) is very relevant.  

---

### Answer by username_7 on 2012-04-25. Score: -4

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?](http://dl.acm.org/citation.cfm?id=1132571) by Impagliazzo 2006

[2] [Natural proofs explained by chris calabro](http://cseweb.ucsd.edu/~ccalabro/essays/nat_pfs.pdf)

[3] [2009 workshop on impagliazzos 5 worlds](http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/)


---

