Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
It helps if you consider the definition of "truly random" first. –  Sadeq Dousti Sep 13 '10 at 17:49
add comment

7 Answers 7

up vote 40 down vote accepted

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.

share|improve this answer
8  
what a beautiful answer. –  Suresh Venkat Sep 17 '10 at 16:57
    
Thanks! This is wonderful. –  arnab Sep 17 '10 at 22:15
1  
I am very appreciative of the clarity of your detailed response on this (to me!) tangled question. Thanks! –  Joseph O'Rourke Sep 18 '10 at 1:16
add comment

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 gives a pop-sci explanation of this issue, in greater detail.

Irrelevant point: I enjoy your column. :-)

share|improve this answer
add comment

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.

share|improve this answer
    
Link to book here: amazon.com/… –  Suresh Venkat Sep 13 '10 at 21:26
    
Thanks, Ian & Suresh, I am retrieving that book from our library! –  Joseph O'Rourke Sep 13 '10 at 22:02
    
Another great book is Nies's "Computability and randomness". –  Diego de Estrada Sep 14 '10 at 23:49
add comment

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

share|improve this answer
    
Ha! Great quote, Jeff! And with a substantive point. –  Joseph O'Rourke Sep 15 '10 at 12:21
add comment

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.

share|improve this answer
    
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 Sep 15 '10 at 12:20
    
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 Sep 15 '10 at 15:00
    
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 Sep 15 '10 at 15:53
add comment

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. If the TM can use arbitrarily large-but-finite resources, then you're in the world of 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.)

share|improve this answer
    
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 Sep 15 '10 at 4:11
    
Thanks, Aaron, the mention of randomness oracle hierarchies is useful. –  Joseph O'Rourke Sep 15 '10 at 12:22
    
@Suresh: I meant a source of randomness. –  Joseph O'Rourke Sep 15 '10 at 13:46
    
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 Sep 15 '10 at 14:16
add comment

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). In contrast, we can get an FPRAS for this problem using sampling. Is this an example of the separation you are looking for ?

share|improve this answer
    
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 Sep 15 '10 at 17:17
    
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 Sep 15 '10 at 17:29
    
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 Sep 15 '10 at 17:43
    
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 Sep 15 '10 at 18:22
    
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 Sep 16 '10 at 4:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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