<p>Intuitively, "random" means "unpredictable", and any sequence generated by a Turing machine can be predicted by running the machine, so Turing machines cannot produce "truly random" numbers.  There are a number of formal definitions of random sequences (randomness only really makes sense as the length of a string goes to infinity), all of which are essentially equivalent.  Perhaps the most natural of these are Martin-Lof randomness, which means that a sequence passes all possible computable statistical tests for stochasticity, and Chaitin random which means that all initial subsequences are incompressible (more specifically, have high Kolmogorov complexity).  In both of these definitions it is incomputable to both generate random sequences and to recognize them.  See the book "Information and Randomness: An Algorithmic Perspective" by Calude for a thorough treatment of this topic.</p>

CC BY-SA 2.5
2010-09-13T21:26:13.063Z
Link to book here: http://www.amazon.com/Information-Randomness-Algorithmic-Perspective-Theoretical/dp/3540434666
Suresh Venkat
CC BY-SA 2.5
2010-09-13T22:02:46.903Z
Thanks, Ian & Suresh, I am retrieving that book from our library!
Joseph O'Rourke
CC BY-SA 2.5
2010-09-14T23:49:59.300Z
Another great book is Nies's "Computability and randomness".
didest
CC BY-SA 2.5
2010-09-13T21:20:50.263Z
2010-09-13T21:20:50.263Z
Ian
<blockquote>
  <p>Any one who considers arithmetical
  methods of producing random digits is,
  of course, in a state of sin.  For, as
  has been pointed out several times,
  there is no such thing as a random
  number — there are only methods to
  produce random numbers, and a strict
  arithmetic procedure of course is not
  such a method. <em>— John von Neumann</em></p>
</blockquote>

CC BY-SA 2.5
2010-09-15T12:21:27.287Z
Ha! Great quote, Jeff!  And with a substantive point.
Joseph O'Rourke
CC BY-SA 2.5
2010-09-14T20:35:07.420Z
2010-09-14T20:35:07.420Z
Jeffε
<p>There is (perhaps) a distinction to be made between "Turing computable" and "effectively computable" in order to answer your question.  If one defines "random process" as "a process that cannot be predicted, no matter what resources we have," and one defines "deterministic process" as "predictable process, given the input and access to (maybe a lot of) resources," then no Turing computable function can be random, because if we knew the Turing machine and simulated it, we could always predict the outcome of the next "experiment" of the process.</p>

<p>In this framework, a Martin-Lof test can be seen as a deterministic process, and the definition of a random sequence is precisely a sequence whose behavior is not predicted by any Martin-Lof test/Turing computable/deterministic process.</p>

<p>This, however, begs the question: "Is a random sequence effectively calculable, in real life?"  There is, in fact, an industry here.  There are published CD's with billions of random (?) bits on them that are used to perform computer simulations of physical systems, etc.  These CD's guarantee that their sequences of bits pass a bunch of Martin-Lof tests.  The book <a href="http://rads.stackoverflow.com/amzn/click/0375424040">The Drunkard's Walk: How Randomness Rules our Lives</a> gives a pop-sci explanation of this issue, in greater detail.</p>

<p>Irrelevant point: I enjoy your column. :-)</p>

CC BY-SA 2.5
2010-09-13T19:59:37.130Z
2010-09-13T19:59:37.130Z
Aaron Sterling
<p>It seems like no one has answered your addendum, so I'll take a shot at it:</p>

<blockquote>
  <p>If I may extend the question a bit in this addendum: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?</p>
</blockquote>

<p>I'm going to try to make the question more precise, and then answer it. (My version might not be what you had in mind though, so let me know if it isn't.)</p>

<p>We have a deterministic TM with access to a random number generator. This TM now computes some function (an actual function, i.e., a deterministic map from an input space to an output space) making use of the random number generator in some way. </p>

<p>So is the TM with access to randomness allowed to make error? If not, then the DTM must give the correct answer no matter what random bits it was supplied. In this case the random bits are unnecessary, as you could just take the random string to be 00000...</p>

<p>If the DTM is allowed to make error, but should get the right answer more often than random guessing, then we can still do without the randomness source. This DTM computes the function $f_i(x,r)$, where x is the input, r is the random string it got from the oracle, and the $f_i$s are the bits of the output. The DTM can now loop over all possible strings $r$ and see what the majority output is, and output that.</p>

CC BY-SA 2.5
2010-09-15T12:20:59.927Z
I find this insightful: "If not, then the DTM must give the correct answer no matter what random bits it was supplied."  Thanks!
Joseph O'Rourke
CC BY-SA 2.5
2010-09-15T15:00:41.807Z
Actually I don't get this.  You seem to be suggesting that P = ZPP or that a randomized algorithm with zero error (for example a las Vegas algorithm) must be deterministic ?
Suresh Venkat
CC BY-SA 2.5
2010-09-15T15:53:59.360Z
By a DTM with oracle access deciding a language, I assumed that the DTM halts after a finite amount of time. In this case, we can get rid of the oracle. For zero-error, we just replace it with 0000..., and for any other purpose one can brute force over all finite length random strings. (I'm sure someone probably holds the opinion that Las Vegas algorithms are not really algorithms since they don't necessarily terminate.)
Robin Kothari
CC BY-SA 2.5
2010-09-14T02:23:59.020Z
2010-09-14T02:23:59.020Z
Robin Kothari
<p>Regarding your "edit question": it makes a big difference if you are asking about computability or complexity.  If there are complexity bounds on the TM, then you obtain the so-called <a href="http://en.wikipedia.org/wiki/Random_oracle">random oracle model</a>.  If the TM can use arbitrarily large-but-finite resources, then you're in the world of <a href="http://en.wikipedia.org/wiki/Algorithmic_randomness#Relative_randomness">relative randomness</a>: there are randomness hierarchies of oracles, much as there are Turing degrees.  (Side point: one of the (in)famous critiques by Koblitz and Menzes was about the use of the random oracle model, so your meta-question is touching on recent academic debates.)</p>

CC BY-SA 2.5
2010-09-15T04:11:54.813Z
Just to clarify though: did Joe want a random oracle (which is essentially a random hash function) or merely a source of randomness ? these are not the same thing, are they ?
Suresh Venkat
CC BY-SA 2.5
2010-09-15T12:22:32.240Z
Thanks, Aaron, the mention of randomness oracle hierarchies is useful.
Joseph O'Rourke
CC BY-SA 2.5
2010-09-15T13:46:12.253Z
@Suresh: I meant a source of randomness.
Joseph O'Rourke
CC BY-SA 2.5
2010-09-15T14:16:47.917Z
You both are probably way ahead of me here, but I was trying to say that randomness needs to be defined relative to a "frame of reference," i.e., the resources available to make predictions. A "source of randomness" might be random with respect to a Turing machine, but not with respect to the Halting Oracle.  I agree with Robin Kothari's answer; my point only was that a "pure source of randomness" seems not to exist under current definitions, because we could always diagonalize against it and obtain something random-er.
Aaron Sterling
CC BY-SA 2.5
2010-09-14T21:37:38.223Z
2010-09-14T21:37:38.223Z
Aaron Sterling
<p>I'm still trying to understand your modified question, especially what limits you place on the TM. So while this answer might not get at exactly what you want, maybe it will help narrow things a bit.</p>
<p>We know that there is an <strong>unconditional</strong> impossibility result for approximating to with a subexponential factor the volume of a convex body deterministically (this is an old result by <a href="https://doi.org/10.1007/BF02187886" rel="nofollow noreferrer">Bárány and Füredi</a>). In contrast, <a href="https://doi.org/10.1145/102782.102783" rel="nofollow noreferrer">we can get an FPRAS</a> for this problem using sampling. Is this an example of the separation you are looking for ?</p>

CC BY-SA 2.5
2010-09-15T17:17:43.693Z
This result is for polynomial time algorithms, right? I interpreted the OP's question as one about computability theory, not complexity theory. By which I mean I interpreted it to mean "Is the set of problems solved by a DTM + source of randomness larger than those solved by a DTM?"
Robin Kothari
CC BY-SA 2.5
2010-09-15T17:29:05.060Z
this is possible. Hence my attempt to flesh it out in more detail. At the computability level, a discrepancy would to me invalidate the Church-Turing thesis though.
Suresh Venkat
CC BY-SA 2.5
2010-09-15T17:43:21.260Z
I like that volume example!  Although I asked specifically about computability theory, I am also interested in complexity differences.  I don't see how this could invalidate C-T, because the previous answers established that a pure source of true randomness is not computable...?
Joseph O'Rourke
CC BY-SA 2.5
2010-09-15T18:22:28.103Z
I think once we formalize what we mean by a DTM with access to a source of randomness (with is its acceptance criteria, halting probability, etc.), we should be able to show that this model also computes exactly the recursive languages.
Robin Kothari
CC BY-SA 2.5
2010-09-16T04:55:05.513Z
True (in the comutable realm). But now I wonder: suppose we construct a string that whose ith bit is the outcome of running the ith turing machine on an encoding of itself. Would being able to predict this string correspond to solving the Halting problem, and is this string random in the Martin-Lof sense ?
Suresh Venkat
CC BY-SA 4.0
2010-09-15T17:00:58.703Z
2022-10-04T20:14:17.757Z
2022-10-04T20:14:17.757Z
Suresh Venkat
<p>I am joining the discussion fairly late, but I will try to address several questions that were asked earlier.</p>

<p>First, as observed by Aaron Sterling, it is important to first decide what we mean by "truly random" numbers, and especially if we are looking at things from a computational complexity or computability perspective.</p>

<p>Let me argue however that in complexity theory, people are mainly interested in <strong>pseudo</strong>-randomness, and <strong>pseudo</strong>-random generators, i.e. functions from strings to strings such that the distribution of the output sequences cannot be told apart from the uniform distribution by some <em>efficient</em> process (where several meanings of <strong>efficient</strong> can be considered, e.g. polytime computable, polynomial-size circuits etc). It is a beautiful and very active research area, but I think most people would agree that the objects it studies are not truly random, it is enough that they just <strong>look</strong> random (hence the term "pseudo"). </p>

<p>In computability theory, a concensus has emerged to what should be a good notion of "true randomness", and it is indeed the notion of Martin-Löf randomness which prevailed (other ones have been proposed and are interesting to study but do not bare all the nice properties Martin-Löf randomness has). To simplify matters, we will consider randomness for infinite binary sequences (other objects such as functions from strings to strings can easily be encoded by such sequence). </p>

<p>An infinite binary sequence $\alpha$ is Martin-Löf random if <strong>no</strong> computable process  (even if we allow this process to be computable in triple exponential time or higher) can detect a randomness flaw. </p>

<p>(1) What do we mean by "randomness flaw"? That part is easy: it is a set of measure 0, i.e. a property that almost all sequences do not have (here we talk about <strong>Lebesgue measure</strong> i.e. the measure where each bit has a $1/2$ probability to be $0$ independently of all the other bits). An example of such a flaw is "having asymptotically 1/3 of zeroes and 2/3 of ones", which violates the law of large numbers. Another example is "for every n, the first 2n bits of $\alpha$ are perfectly distributed (as many zeroes as ones)". In this case the law of large numbers is satified, but not the central limit theorem. Etc etc.<br>
(2) How can a computable process test that a sequence does not belong to a particular set of measure 0? In other words, what sets of measure 0 can be computably described? This is precisely what Martin-Löf tests are about. A Martin-Löf test is a computable procedure which, given an input k, computably (i.e., via a Turing machine with input $k$) generates a sequence of strings $w_{k,0}$, $w_{k,1}$, ... such that the set $U_k$ of infinite sequences starting by one of those $w_{k,i}$ has measure at most $2^{-k}$ (if you like topology, notice that this is an open set in the product topology for the set of infinite binary sequences). Then the set $G=\bigcap_k U_k$ has measure $0$ and is referred to as <strong>Martin-Löf nullset</strong>. We can now define Martin-Löf randomness by saying that <strong>an infinite binary sequence $\alpha$ is Martin-Löf random if it does not belong to any Martin-Löf nullset</strong>.  </p>

<p>This definition might seem technical but it is widely accepted as being the right one for several reasons:</p>

<ul>
<li>it is effective enough, i.e. its definition involves computable processes</li>
<li>it is strong enough: any "almost sure" property you may find in a probability theory textbook (law of large numbers, law of iterated logarithm, etc) can be tested by a Martin-Löf test (although this is sometimes hard to prove)</li>
<li>it has been independently proposed by several people using different definitions (in particular the Levin-Chaitin definition using Kolmogorov complexity); and the fact that they all lead to the same concept is a hint that it should be the right notion (a little bit like the notion of computable function, which can be defined via Turing machines, recursive functions, lambda-calculus, etc.) </li>
<li>the mathematical theory behind it is very nice! see the three excellent books <em>An Introduction to Kolmogorov Complexity and Its Applications</em> (Li and Vitanyi), <em>Algorithmic randomness and complexity</em> (Downey and Hirschfeldt) <em>Computability and Randomness</em> (Nies).</li>
</ul>

<p>What does a Martin-Löf random sequence look like? Well, take a perfectly balanced coin and start flipping it. At each flip, write a 0 for heads and a 1 for tails. Continue until the end of time. That's what a Martin-Löf sequence looks like :-) </p>

<p>Now back to the initial question: is there a computable way to generate a Martin-Löf random sequence? Intuitively the answer should be <strong>NO</strong>, because if we can use a computable process to generate a sequence $\alpha$, then we can certainly use a computable process to describe the singleton {$\alpha$}, so $\alpha$ is not random. Formally this is done as follows. Suppose a sequence $\alpha$ is computable. Consider the following Martin-Löf test: for all $k$, just output the prefix $a_k$ of $\alpha$ of length $k$, and nothing else. This has measure at most (in fact, exactly) $2^{-k}$, and the intersection of the sets $U_k$ as in the definition is exactly {${\alpha}$}. QED!!</p>

<p>In fact a Martin-Löf random sequence $\alpha$ is incomputable in a much stronger sense: if some oracle computation with oracle $\beta$ (which itself is an infinite binary sequence) can compute $\alpha$, then for all $n$, $n-O(1)$ bits of $\beta$ are needed to compute the first $n$ bits of $\alpha$ (this is in fact a <strong>characterization</strong> of Martin-Löf randomness, which unfortunately is rarely stated as is in the literature). </p>

<hr>

<p>Ok, now the "edit" part of Joseph's question: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?</p>

<p>From a computability perspective, the answer is "yes and no". If you are given access to a random source as an oracle (where the output is presented as an infinite binary sequence), with probability 1 you will get a Martin-Löf random oracle, and as we saw earlier Martin-Löf random implies non-computable, so it suffices to output the oracle itself! Or if you want a function $f: \mathbb{N} \rightarrow \mathbb{N}$, you can consider the function $f$ which for all $n$ tells you how many zeroes there are among the first $n$ bits of your oracle. If the oracle is Martin-Löf random, this function will be non-computable. </p>

<p>But of course you might argue that this is cheating: indeed, for a different oracle we might get a different function, so there is a non-reproducibility problem. Hence another way to understand your question is the following: is there a function $f$ which is non-computable, but which can be "computed with positive probability", in the sense that there is an Turing machine with access to a random oracle which, with positive probability (over the oracle), computes $f$. The answer is no, due to a theorem of Sacks whose proof is quite simple. Actually it has mainly been answered by Robin Kothari: if the probability for the TM to be correct is greater than 1/2, then one can look for all $n$ at all the possible oracle computations with input $n$ and find the output which gets the "majority vote", i.e. which is produced by a set of oracles of measure more than 1/2 (this can be done effectively). The argument even extend to smaller probabilities: suppose the TM outputs $f$ with probability $\epsilon >0$. By Lebesgue's density theorem, there exists a finite string $\sigma$ such that if we fix the first bits of the oracle to be exactly $\sigma$, and then get the other bits at random, then we compute $f$ with probability at least 0.99. By taking such a $\sigma$, we can apply the above argument again. </p>

CC BY-SA 2.5
2010-09-17T16:57:22.210Z
what a beautiful answer.
Suresh Venkat
CC BY-SA 2.5
2010-09-18T01:16:30.603Z
I am very appreciative of the clarity of your detailed response on this (to me!) tangled question.  Thanks!
Joseph O'Rourke
CC BY-SA 2.5
2010-09-17T16:08:31.163Z
2010-09-17T17:05:40.980Z
2010-09-17T17:05:40.980Z
LaurentBienvenu
<p>I am seeking a definitive answer to whether or not generation of "truly random" numbers
is Turing computable.  I don't know how to phrase this precisely.
<a href="https://cstheory.stackexchange.com/questions/476/what-are-the-most-effective-algorithms-to-find-random-number">This StackExchange question</a> on "efficient algorithms for random number generation"
comes close to answering my question.
Charles Stewart says in his answer, "it [Martin-Löf randomness] cannot be generated by a machine." Ross Snider says, "any deterministic process (such as Turing/Register Machines) can not produce 'philosophical' or 'true' random numbers." Is there a clear and accepted notion of what constitutes a truly random number generator?
And if so, is it known that it cannot be computed by a Turing Machine?</p>

<p>Perhaps pointing me to the relevant literature would suffice.  Thanks for any help you can provide!</p>

<p><b>Edit.</b> Thanks to Ian and Aaron for the knowledgeable answers!  I am relatively unschooled in this area, and I am grateful for the assistance. If I may extend the question a bit in this addendum: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?</p>

CC BY-SA 4.0
2023-11-27T15:38:16.683Z
The answers to this question are quite satisfactory, but don't really provide citable references. “Fact ①” from [this other question](https://cstheory.stackexchange.com/q/53598/17747) provides a few for the fact that “if $L$ is computable by a non-measure-zero set of oracles, then it is computable”: Sacks, *Degrees of Unsolvability* (1963), §10, theorem 1 (p. 154); Nies, *Computability and Randomness* (2009), theorem 5.1.12 (p. 169); or Downey & Hirschfeldt, *Algorithmic Randomness and Complexity* (2010), corollary 8.2.12 (p. 358).
Gro-Tsen
CC BY-SA 2.5
2010-09-13T17:49:25.490Z
It helps if you consider the definition of "truly random" first.
Sadeq Dousti
<reference-request><computability><turing-machines><randomness>
Truly random number generator: Turing computable?
Joseph O'Rourke
# Truly random number generator: Turing computable?

(Asked by: username_0 on 2010-09-13)

I am seeking a definitive answer to whether or not generation of "truly random" numbers
is Turing computable. I don't know how to phrase this precisely.
[This StackExchange question](https://cstheory.stackexchange.com/questions/476/what-are-the-most-effective-algorithms-to-find-random-number) on "efficient algorithms for random number generation"
comes close to answering my question.
Charles Stewart says in his answer, "it [Martin-Löf randomness] cannot be generated by a machine." Ross Snider says, "any deterministic process (such as Turing/Register Machines) can not produce 'philosophical' or 'true' random numbers." Is there a clear and accepted notion of what constitutes a truly random number generator?
And if so, is it known that it cannot be computed by a Turing Machine?

Perhaps pointing me to the relevant literature would suffice. Thanks for any help you can provide!

**Edit.** Thanks to Ian and Aaron for the knowledgeable answers! I am relatively unschooled in this area, and I am grateful for the assistance. If I may extend the question a bit in this addendum: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?

**Tags:** reference-request, computability, turing-machines, randomness
> **Comments:**
> **username_2**: It helps if you consider the definition of "truly random" first.  
> **username_1**: The answers to this question are quite satisfactory, but don't really provide citable references. “Fact ①” from [this other question](https://cstheory.stackexchange.com/q/53598/17747) provides a few for the fact that “if $L$ is computable by a non-measure-zero set of oracles, then it is computable”: Sacks, *Degrees of Unsolvability* (1963), §10, theorem 1 (p. 154); Nies, *Computability and Randomness* (2009), theorem 5.1.12 (p. 169); or Downey & Hirschfeldt, *Algorithmic Randomness and Complexity* (2010), corollary 8.2.12 (p. 358).  

---

## 7 answers

### Answer by username_9 on 2010-09-17. Score: 63 | Accepted answer

I am joining the discussion fairly late, but I will try to address several questions that were asked earlier.

First, as observed by Aaron Sterling, it is important to first decide what we mean by "truly random" numbers, and especially if we are looking at things from a computational complexity or computability perspective.

Let me argue however that in complexity theory, people are mainly interested in **pseudo**-randomness, and **pseudo**-random generators, i.e. functions from strings to strings such that the distribution of the output sequences cannot be told apart from the uniform distribution by some *efficient* process (where several meanings of **efficient** can be considered, e.g. polytime computable, polynomial-size circuits etc). It is a beautiful and very active research area, but I think most people would agree that the objects it studies are not truly random, it is enough that they just **look** random (hence the term "pseudo").

In computability theory, a concensus has emerged to what should be a good notion of "true randomness", and it is indeed the notion of Martin-Löf randomness which prevailed (other ones have been proposed and are interesting to study but do not bare all the nice properties Martin-Löf randomness has). To simplify matters, we will consider randomness for infinite binary sequences (other objects such as functions from strings to strings can easily be encoded by such sequence).

An infinite binary sequence $\alpha$ is Martin-Löf random if **no** computable process (even if we allow this process to be computable in triple exponential time or higher) can detect a randomness flaw.

(1) What do we mean by "randomness flaw"? That part is easy: it is a set of measure 0, i.e. a property that almost all sequences do not have (here we talk about **Lebesgue measure** i.e. the measure where each bit has a $1/2$ probability to be $0$ independently of all the other bits). An example of such a flaw is "having asymptotically 1/3 of zeroes and 2/3 of ones", which violates the law of large numbers. Another example is "for every n, the first 2n bits of $\alpha$ are perfectly distributed (as many zeroes as ones)". In this case the law of large numbers is satified, but not the central limit theorem. Etc etc.  
(2) How can a computable process test that a sequence does not belong to a particular set of measure 0? In other words, what sets of measure 0 can be computably described? This is precisely what Martin-Löf tests are about. A Martin-Löf test is a computable procedure which, given an input k, computably (i.e., via a Turing machine with input $k$) generates a sequence of strings $w\_{k,0}$, $w\_{k,1}$, ... such that the set $U\_k$ of infinite sequences starting by one of those $w\_{k,i}$ has measure at most $2^{-k}$ (if you like topology, notice that this is an open set in the product topology for the set of infinite binary sequences). Then the set $G=\bigcap\_k U\_k$ has measure $0$ and is referred to as **Martin-Löf nullset**. We can now define Martin-Löf randomness by saying that **an infinite binary sequence $\alpha$ is Martin-Löf random if it does not belong to any Martin-Löf nullset**.

This definition might seem technical but it is widely accepted as being the right one for several reasons:

* it is effective enough, i.e. its definition involves computable processes
* it is strong enough: any "almost sure" property you may find in a probability theory textbook (law of large numbers, law of iterated logarithm, etc) can be tested by a Martin-Löf test (although this is sometimes hard to prove)
* it has been independently proposed by several people using different definitions (in particular the Levin-Chaitin definition using Kolmogorov complexity); and the fact that they all lead to the same concept is a hint that it should be the right notion (a little bit like the notion of computable function, which can be defined via Turing machines, recursive functions, lambda-calculus, etc.)
* the mathematical theory behind it is very nice! see the three excellent books *An Introduction to Kolmogorov Complexity and Its Applications* (Li and Vitanyi), *Algorithmic randomness and complexity* (Downey and Hirschfeldt) *Computability and Randomness* (Nies).

What does a Martin-Löf random sequence look like? Well, take a perfectly balanced coin and start flipping it. At each flip, write a 0 for heads and a 1 for tails. Continue until the end of time. That's what a Martin-Löf sequence looks like :-)

Now back to the initial question: is there a computable way to generate a Martin-Löf random sequence? Intuitively the answer should be **NO**, because if we can use a computable process to generate a sequence $\alpha$, then we can certainly use a computable process to describe the singleton {$\alpha$}, so $\alpha$ is not random. Formally this is done as follows. Suppose a sequence $\alpha$ is computable. Consider the following Martin-Löf test: for all $k$, just output the prefix $a\_k$ of $\alpha$ of length $k$, and nothing else. This has measure at most (in fact, exactly) $2^{-k}$, and the intersection of the sets $U\_k$ as in the definition is exactly {${\alpha}$}. QED!!

In fact a Martin-Löf random sequence $\alpha$ is incomputable in a much stronger sense: if some oracle computation with oracle $\beta$ (which itself is an infinite binary sequence) can compute $\alpha$, then for all $n$, $n-O(1)$ bits of $\beta$ are needed to compute the first $n$ bits of $\alpha$ (this is in fact a **characterization** of Martin-Löf randomness, which unfortunately is rarely stated as is in the literature).

---

Ok, now the "edit" part of Joseph's question: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?

From a computability perspective, the answer is "yes and no". If you are given access to a random source as an oracle (where the output is presented as an infinite binary sequence), with probability 1 you will get a Martin-Löf random oracle, and as we saw earlier Martin-Löf random implies non-computable, so it suffices to output the oracle itself! Or if you want a function $f: \mathbb{N} \rightarrow \mathbb{N}$, you can consider the function $f$ which for all $n$ tells you how many zeroes there are among the first $n$ bits of your oracle. If the oracle is Martin-Löf random, this function will be non-computable.

But of course you might argue that this is cheating: indeed, for a different oracle we might get a different function, so there is a non-reproducibility problem. Hence another way to understand your question is the following: is there a function $f$ which is non-computable, but which can be "computed with positive probability", in the sense that there is an Turing machine with access to a random oracle which, with positive probability (over the oracle), computes $f$. The answer is no, due to a theorem of Sacks whose proof is quite simple. Actually it has mainly been answered by Robin Kothari: if the probability for the TM to be correct is greater than 1/2, then one can look for all $n$ at all the possible oracle computations with input $n$ and find the output which gets the "majority vote", i.e. which is produced by a set of oracles of measure more than 1/2 (this can be done effectively). The argument even extend to smaller probabilities: suppose the TM outputs $f$ with probability $\epsilon >0$. By Lebesgue's density theorem, there exists a finite string $\sigma$ such that if we fix the first bits of the oracle to be exactly $\sigma$, and then get the other bits at random, then we compute $f$ with probability at least 0.99. By taking such a $\sigma$, we can apply the above argument again.

> **Comments:**
> **username_4**: what a beautiful answer.  
> **username_0**: I am very appreciative of the clarity of your detailed response on this (to me!) tangled question.  Thanks!  

---

### Answer by username_3 on 2010-09-13. Score: 12

Intuitively, "random" means "unpredictable", and any sequence generated by a Turing machine can be predicted by running the machine, so Turing machines cannot produce "truly random" numbers. There are a number of formal definitions of random sequences (randomness only really makes sense as the length of a string goes to infinity), all of which are essentially equivalent. Perhaps the most natural of these are Martin-Lof randomness, which means that a sequence passes all possible computable statistical tests for stochasticity, and Chaitin random which means that all initial subsequences are incompressible (more specifically, have high Kolmogorov complexity). In both of these definitions it is incomputable to both generate random sequences and to recognize them. See the book "Information and Randomness: An Algorithmic Perspective" by Calude for a thorough treatment of this topic.

> **Comments:**
> **username_4**: Link to book here: http://www.amazon.com/Information-Randomness-Algorithmic-Perspective-Theoretical/dp/3540434666  
> **username_0**: Thanks, Ian & Suresh, I am retrieving that book from our library!  
> **username_5**: Another great book is Nies's "Computability and randomness".  

---

### Answer by username_6 on 2010-09-14. Score: 12

> Any one who considers arithmetical
> methods of producing random digits is,
> of course, in a state of sin. For, as
> has been pointed out several times,
> there is no such thing as a random
> number — there are only methods to
> produce random numbers, and a strict
> arithmetic procedure of course is not
> such a method. *— John von Neumann*

> **Comments:**
> **username_0**: Ha! Great quote, Jeff!  And with a substantive point.  

---

### Answer by username_7 on 2010-09-13. Score: 12

There is (perhaps) a distinction to be made between "Turing computable" and "effectively computable" in order to answer your question. If one defines "random process" as "a process that cannot be predicted, no matter what resources we have," and one defines "deterministic process" as "predictable process, given the input and access to (maybe a lot of) resources," then no Turing computable function can be random, because if we knew the Turing machine and simulated it, we could always predict the outcome of the next "experiment" of the process.

In this framework, a Martin-Lof test can be seen as a deterministic process, and the definition of a random sequence is precisely a sequence whose behavior is not predicted by any Martin-Lof test/Turing computable/deterministic process.

This, however, begs the question: "Is a random sequence effectively calculable, in real life?" There is, in fact, an industry here. There are published CD's with billions of random (?) bits on them that are used to perform computer simulations of physical systems, etc. These CD's guarantee that their sequences of bits pass a bunch of Martin-Lof tests. The book [The Drunkard's Walk: How Randomness Rules our Lives](http://rads.stackoverflow.com/amzn/click/0375424040) gives a pop-sci explanation of this issue, in greater detail.

Irrelevant point: I enjoy your column. :-)


---

### Answer by username_8 on 2010-09-14. Score: 8

It seems like no one has answered your addendum, so I'll take a shot at it:

> If I may extend the question a bit in this addendum: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?

I'm going to try to make the question more precise, and then answer it. (My version might not be what you had in mind though, so let me know if it isn't.)

We have a deterministic TM with access to a random number generator. This TM now computes some function (an actual function, i.e., a deterministic map from an input space to an output space) making use of the random number generator in some way.

So is the TM with access to randomness allowed to make error? If not, then the DTM must give the correct answer no matter what random bits it was supplied. In this case the random bits are unnecessary, as you could just take the random string to be 00000...

If the DTM is allowed to make error, but should get the right answer more often than random guessing, then we can still do without the randomness source. This DTM computes the function $f\_i(x,r)$, where x is the input, r is the random string it got from the oracle, and the $f\_i$s are the bits of the output. The DTM can now loop over all possible strings $r$ and see what the majority output is, and output that.

> **Comments:**
> **username_0**: I find this insightful: "If not, then the DTM must give the correct answer no matter what random bits it was supplied."  Thanks!  
> **username_4**: Actually I don't get this.  You seem to be suggesting that P = ZPP or that a randomized algorithm with zero error (for example a las Vegas algorithm) must be deterministic ?  
> **username_8**: By a DTM with oracle access deciding a language, I assumed that the DTM halts after a finite amount of time. In this case, we can get rid of the oracle. For zero-error, we just replace it with 0000..., and for any other purpose one can brute force over all finite length random strings. (I'm sure someone probably holds the opinion that Las Vegas algorithms are not really algorithms since they don't necessarily terminate.)  

---

### Answer by username_7 on 2010-09-14. Score: 5

Regarding your "edit question": it makes a big difference if you are asking about computability or complexity. If there are complexity bounds on the TM, then you obtain the so-called [random oracle model](http://en.wikipedia.org/wiki/Random_oracle). If the TM can use arbitrarily large-but-finite resources, then you're in the world of [relative randomness](http://en.wikipedia.org/wiki/Algorithmic_randomness#Relative_randomness): there are randomness hierarchies of oracles, much as there are Turing degrees. (Side point: one of the (in)famous critiques by Koblitz and Menzes was about the use of the random oracle model, so your meta-question is touching on recent academic debates.)

> **Comments:**
> **username_4**: Just to clarify though: did Joe want a random oracle (which is essentially a random hash function) or merely a source of randomness ? these are not the same thing, are they ?  
> **username_0**: Thanks, Aaron, the mention of randomness oracle hierarchies is useful.  
> **username_0**: @Suresh: I meant a source of randomness.  
> **username_7**: You both are probably way ahead of me here, but I was trying to say that randomness needs to be defined relative to a "frame of reference," i.e., the resources available to make predictions. A "source of randomness" might be random with respect to a Turing machine, but not with respect to the Halting Oracle.  I agree with Robin Kothari's answer; my point only was that a "pure source of randomness" seems not to exist under current definitions, because we could always diagonalize against it and obtain something random-er.  

---

### Answer by username_4 on 2010-09-15. Score: 5

I'm still trying to understand your modified question, especially what limits you place on the TM. So while this answer might not get at exactly what you want, maybe it will help narrow things a bit.

We know that there is an **unconditional** impossibility result for approximating to with a subexponential factor the volume of a convex body deterministically (this is an old result by [Bárány and Füredi](https://doi.org/10.1007/BF02187886)). In contrast, [we can get an FPRAS](https://doi.org/10.1145/102782.102783) for this problem using sampling. Is this an example of the separation you are looking for ?

> **Comments:**
> **username_8**: This result is for polynomial time algorithms, right? I interpreted the OP's question as one about computability theory, not complexity theory. By which I mean I interpreted it to mean "Is the set of problems solved by a DTM + source of randomness larger than those solved by a DTM?"  
> **username_4**: this is possible. Hence my attempt to flesh it out in more detail. At the computability level, a discrepancy would to me invalidate the Church-Turing thesis though.  
> **username_0**: I like that volume example!  Although I asked specifically about computability theory, I am also interested in complexity differences.  I don't see how this could invalidate C-T, because the previous answers established that a pure source of true randomness is not computable...?  
> **username_8**: I think once we formalize what we mean by a DTM with access to a source of randomness (with is its acceptance criteria, halting probability, etc.), we should be able to show that this model also computes exactly the recursive languages.  
> **username_4**: True (in the comutable realm). But now I wonder: suppose we construct a string that whose ith bit is the outcome of running the ith turing machine on an encoding of itself. Would being able to predict this string correspond to solving the Halting problem, and is this string random in the Martin-Lof sense ?  

---

