24
$\begingroup$

I know that there are many algorithms to generate pseudorandom numbers but is it possible to generate truly random numbers using a computer program?

$\endgroup$
19
  • 38
    $\begingroup$ What is your definition of "truly random"? $\endgroup$
    – Arthur
    Dec 13, 2016 at 9:55
  • 27
    $\begingroup$ It depends on what you mean by randomness, and your philosophical beliefs on the determinism of the universe. $\endgroup$
    – saleml
    Dec 13, 2016 at 10:01
  • 23
    $\begingroup$ Gently remove the computer program from the computer, and toss it in the air. If it lands right-side-up, record a one, else, a zero. Repeat as necessary to generate your truly random number. $\endgroup$
    – Gerry Myerson
    Dec 13, 2016 at 12:20
  • 15
    $\begingroup$ @Gerry: Next question, is it possible to perform a truly random toss-in-the-air? $\endgroup$
    – user856
    Dec 13, 2016 at 16:26
  • 12
    $\begingroup$ It's not possible for a computer program (a formal construct with a deterministic outcome for a given input) to do this by itself, but a computer, being a physical device in a physical world full of random events, likely has access to measure at least some of those. $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Dec 13, 2016 at 16:31

9 Answers 9

Reset to default
48
$\begingroup$

This is a good question, but to dig into it we have to look at the underlying assumptions.

First, for the purpose at hand, it doesn't really make sense to say that a number itself is random. There is a sense of a particular number being random from Kolmogorov complexity, but that is not what is intended here. Instead, what we are interested in might be called a random process - a process that generates a sequence of numbers so that the sequence satisfies some particular probability distribution. We want to know if a computer can generate a sequence of numbers in a random manner.

The next question is what we mean by "using a computer program". If we take a "computer program" to be a completely deterministic algorithm, then it will not be able to generate numbers in a truly random manner. There is no computer program which could be simulated entirely by paper and pencil - deterministically - which generates numbers in a random manner. The next number in the sequence is always completely predictable!

However, if we are willing to add additional hardware, then it might become able. This is a broader notion of "program". For example, the machines used to draw winning numbers for a lottery are designed, essentially, to try to generate numbers in a random manner. There is no reason that one of these could not be connected to a computer and automated. So, if we accept that the lottery can generate numbers randomly, so can a computer.

There are faster methods, as well. Some operating systems try to gather random information from the environment, store this information, and then return it when asked to generate a random number. This is not a deterministic process, but theoretically it does generate numbers in a random manner. For example, the computer can measure white noise, or can measure the timing of various events like keystrokes and packet arrivals, and combine these in a theoretically valid way to generate numbers randomly.

The final issue is philosophical. Some might believe that the entire universe is deterministic, and therefore nothing is ever random. However, that objection is too far removed for the present conversation. If we want to ask whether computers can generate numbers in a random manner, we normally take it as a given that something could generate numbers in a random manner, so that we can focus on whether computers can do so.

$\endgroup$
1
  • 1
    $\begingroup$ Some computer architectures do include a hardware RNG. For example, Intel x86 hardware since IvyBridge includes the RDRAND instruction, which puts a random number into a CPU register. It happens to be designed as an instruction-set extension, not an I/O device, but the actual implementation is not purely digital logic: the randomness comes from sampling thermal noise. Using this may not count as a "program" according to computer science. $\endgroup$
    – Peter Cordes
    Dec 13, 2016 at 18:15
19
$\begingroup$

After searching the Internet, I have decided to answer my own question here. It is possible to generate truly random numbers. Random numbers are generated from random unpredictable processes like thermal or atmospheric noises, cosmic radiations, etc. We need special hardware or sensors which can measure such processes and there could be a program which can produce a number from the input of random events. As this method uses random events rather than a pre-defined algorithm, it can generate a truly random number.

You can find one such online solution at https://www.random.org/. Random.org uses atmospheric noise to create randomness.

Finally, here is a joke:

Random number

$\endgroup$
8
  • 12
    $\begingroup$ Just to argue the philosophical side; you claim "Random numbers are generated from random unpredictable processes", however, just because they're unpredictable, doesn't necessarily mean that they are random. I think we'll have to settle for "random enough"! $\endgroup$
    – James Webster
    Dec 13, 2016 at 15:19
  • 2
    $\begingroup$ @JamesWebster I agree with you that they might not be random but that's the problem with randomness. You can never be sure ;) $\endgroup$
    – Razin
    Dec 13, 2016 at 16:16
  • 3
    $\begingroup$ Similar joke: xkcd.com/221 $\endgroup$
    – Nayuki
    Dec 13, 2016 at 18:39
  • $\begingroup$ @JamesWebster: Unpredictable is the best we can hope for, as it is impossible in principle to prove that there exists true randomness to begin with (yes, even quantum mechanics doesn't help; there are deterministic interpretations of quantum mechanics). $\endgroup$
    – celtschk
    Dec 13, 2016 at 20:42
  • 2
    $\begingroup$ i find disturbing your answer got so many votes. it's very short and doesn't explain much about randomnes. $\endgroup$
    – Santropedro
    Jan 7, 2017 at 1:44
9
$\begingroup$

Yes from a theoretical point of view, not from a practical point of view.

It is possible with a program accessing the wifi module in off-the-shelf computers. The idea behind this is described here: The random changes in noise level are recorded. This noise is generally accepted as being random (just turn your AM radio to some unoccupied frequency at daytime and listen to the noise the atmosphere produces. The same happens on the ~2 GHz frequencies our wifi modules operate on.). I think they follow some kind of poisson process, so the time between noise changes follows some exponential distribution.

Maybe one could also use turning objects like the cooling fan or the hard disk as some kind of wheel of Fortune since their rotation speed can be controlled and recorded by software.

However, such random numbers tend to have one big drawback: You don't know their true distribution. So they are useless for most applications, except if you take the random number to seed a ordinary pseudo random number generator (pRNG). Then the resulting pseudo random numbers are a bit less "pseudo" but still have a known (frequency) distribution.

Sources of useful randomness with a better understood distribution usually need devices that are no longer part of usual computers. Such devices need to comply to narrow specifications in order to produce the desired probabilities. Usual computers do not: You don't know how much your cooling fan's bearing is worn-out, which random noise your wifi actucally receives etc.

Another downside: Generating real random numbers is much slower than pRNGs are, even if you have a specialized device that observes some radioactive decay in order to produce random numbers. So you may end up again with producing only the seed for the pRNG at random.

$\endgroup$
2
  • 1
    $\begingroup$ Even if you don't know the exact distribution, a post-processing step can correct that. e.g. suppose you have some radioactive-source-Geiger-counter system which is not precisely tuned, so $p(1)\ne p(0)$. Then just read each sequence of two bits; if you get 00 or 11, throw it away; if you get 01, output 0; if you get 10, output 1. That fixes a bias towards 1 or 0. (Of course, the better tuned the Geiger counter is, the more bits you'll get out of the post-processing.) $\endgroup$
    – Daniel Schepler
    Dec 13, 2016 at 23:14
  • 1
    $\begingroup$ @DanielSchepler For this method to work, you have to assume that successive events are independent (or at least uncorrelated), I think. $\endgroup$
    – Federico Poloni
    Dec 13, 2016 at 23:32
6
$\begingroup$

Yes there are random events.

Yes you can use a computer with a computer program to measure these and translate them to numbers.

This way you can have your program outputting truly random numbers

The philosophical question would be: would you have a computer program generating random numbers or a: "phenomena measuring" program where the phenomenon happens to have a random factor.

Because your computer program is definitely not generating randomness, it's merely using it.

$\endgroup$
2
  • $\begingroup$ You mean like the Linux kernel's /dev/random driver, which accumulates randomness from the timing of interrupts and other events? (e.g. sample the low bits of a high-resolution clock when network packets arrive, on every keypress, and similar stuff that shouldn't be correlated with the clock. It mixes those small amounts of randomness into an entropy pool. en.wikipedia.org/wiki//dev/random#Linux) $\endgroup$
    – Peter Cordes
    Dec 13, 2016 at 17:59
  • $\begingroup$ @PeterCordes Exactly, the driver, doesn't generate random data, it collects it. $\endgroup$
    – Pieter B
    Dec 13, 2016 at 18:44
5
$\begingroup$

The answer is no, but you first need to give a precise definition of randomness. I suggest you to read the wikipedia entry Algorithmically random sequence. If you use Martin-Löf's definition (a sequence is random if there is a uniform bound on the compressibility of its initial segments), it can be proved that no random sequence is decidable, computably enumerable, or co-computably-enumerable.

$\endgroup$
7
  • 2
    $\begingroup$ This would not, on its own, stop a computer from generating one, because a computer could use additional devices (e.g. dice, or a machine like a lottery uses to draw winning numbers) which, depending on deeper questions about the universe, might be able to generate sequences in a truly random manner. $\endgroup$
    – Carl Mummert
    Dec 13, 2016 at 12:08
  • 1
    $\begingroup$ The question specifies "using a computer program". This does not allow additional devices, in my understanding. $\endgroup$
    – J.-E. Pin
    Dec 13, 2016 at 12:29
  • 1
    $\begingroup$ That is a confusion in the question, I agree. Is a program that reads from another device a program? To quote Shakespeare, "If you execute it, does it not run?" $\endgroup$
    – Carl Mummert
    Dec 13, 2016 at 12:31
  • 2
    $\begingroup$ Let us wait for the input of the OP to know exactly what he had in mind. $\endgroup$
    – J.-E. Pin
    Dec 13, 2016 at 12:40
  • 3
    $\begingroup$ @MathematicsStudent1122 Our understanding of the world has made substantial progress since 1814. $\endgroup$
    – Peter - Reinstate Monica
    Dec 13, 2016 at 13:47
5
$\begingroup$

I do know of one tool that uses radioactive decay to generate true random numbers, found here.

Generating true randomness from a simple computer with no extra hardware is not possible to my knowledge.

$\endgroup$
3
4
$\begingroup$

Anyone with some I/O programming skills would be able to generate it. Not intending to patent it :-( therefore, every time you need a random number run the following algorithm:

  1. Move to a noisy place. The noisier the better; the more different noises you can listen the better, try not to use a place where a single big noise is dominating. A NY or most big cities at noon would be fine (you don’t really need to bother a lot with that, moving to your balcony may be enough);
  2. Turn on your device microphone;
  3. Record the noise;
  4. Digitize the recorded signal;
  5. Normalize to the highest value of the recorded noise i.e., highest value=1;
  6. Take the value on the $\rm n^{th}$ second of recording (provided you have recorded at least $\rm n$ seconds of noise obviously), for example the value in the $\rm 5^{th}$ second. Let’s name this value as $\rm V$, therefore $\rm V=V(n)$. Ideally $\rm n$ should be generated by any (pseudo)random number generator of your programming language or API’s you are using, giving you a second layer of randomness.
  7. Multiply $\rm V$ with the Highest Integer (or float if you want) that your system provides and your Random number $\rm R$ will be $\rm R=V×Integer.MaxValue$.

UPDATE: For a truly random number, create a background worker and repeat this algorithm in an infinite loop. However, this time use the live streaming from your device (or attached) microphone and not a record. Therefore any time someone interrupts you he will actually help you by providing (unexpected) noise. The same happens if your neighbor call his son, or close is car dor. Present moment cannot be repeated absolutely. This even solves the problem of needing many random numbers.

$\endgroup$
4
  • $\begingroup$ How do you choose the value of $n$ in step 6? $\endgroup$
    – MasB
    Dec 13, 2016 at 18:26
  • $\begingroup$ @BernardMassé $\rm n$ Is any time value between 0 seconds and track length. In my answer I put the example on $\rm t=5secs$ provided you have at least 5 seconds of recording. Just for the sake of clarity Randomness is not in choosing this value but in the function $\rm V(n)$ which is no other than the intensity of sound in that particular moment. Still you don't miss anything if you choose it using your programming language (pseudo)random number generator, as long as it is within that range. $\endgroup$
    – J. Manuel
    Dec 13, 2016 at 19:59
  • $\begingroup$ You would have to do a Fourier treansform of the noise. Any "spikes" in the frequency vs amplitude plot would indicate that the noise is not truely random. $\endgroup$
    – Steven Alexis Gregory
    Dec 14, 2016 at 2:46
  • $\begingroup$ @StevenGregory Great. It will improve the algorithm. A simplistic algorithm like this is (just) intended to show that such truly random numbers may be "realistically" achieved. $\endgroup$
    – J. Manuel
    Dec 14, 2016 at 8:06
2
$\begingroup$

Yes, but there must be some random input. For example, the program can ask the user for a random number and then print it to the screen. Most of the other answers are sophisticated variants on this.

A deterministic Turing machine with a given "input" (initial tape, state of memory or whatever it is) will not generate random numbers.

$\endgroup$
1
$\begingroup$

In our cybersecurity lecture we were told, that you could use the way somebody types on his keyboard as a generator for pseudorandomness and then use the Von-Neumann-Correctur to get a real random number.

Von-Neumann-Correctur: Take two outputs from the biased pseudorandom generator.

If they are (00) or (11) throw them away and query new ones. If they are (10) output 1 and for (01) output 0.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .