Is there a software algorithm can generate a non-deterministic pattern or sequence? In Chaos theory, simple processes can create deterministic patterns, and psudo-random number generators can generate deterministic numbers with the same seed. Is there a software algorithm that can create completely non-deterministic patterns or sequences? Does it require hardware such as a quantum random number generator?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
No deterministic algorithm can generate a non-deterministic output.
A non-deterministic algorithm (e.g., a NDFA) could, but they exist only in theory, not in practice.
An algorithm with access to a random number generator can generate a random output, and therefore its output is not deterministic. For instance, in practice by reading from /dev/urandom or CryptGenRandom(), you can get random bits, which can be used to produce random output, or to seed a pseudorandom number generator. (You don't need a quantum random number generator to get random numbers.)
Chaos theory is pretty much irrelevant here.
$\begingroup$
$\endgroup$
2
D.W's answer is absolutely correct in the strict sense of how it's written. The key words are "deterministic algorithm".
However and this is crucial, your question relates to "software algorithm". We have to assume that software executes on hardware, and this is a computer forum after all. If you make this simple paradigm shift, then the answer becomes yes, there are software algorithms that are non deterministic.
In fact and in the general case, all running software algorithms are entirely non deterministic on the micro scale. The best that can be achieved is to put arbitrary bounds on the duration of processes as done in real time operating systems.
This all stems from the fact that there really is no such thing as digital or binary electronics. All electronics are analogue, even the machine you're using to read this. It takes a finite amount of time for a signal level to rise from a "0" to a "1". It then takes another finite period of time for the signal to pass from one side a circuit to another. Quantum, environmental, temporal and manufacturing parameters all affect the transition time. The notion of digital electronics arises from wanting only two predominant states, whilst trying to minimise the analogue ones.
Then you have to consider that a modern CPU is complicated. It doesn't just plod along running a single program. There is pipelining, parallel and speculative execution and multi level caching. And myriad other things that all interact and make exact microscopic prediction impossible. Language features such as garbage collection further obfuscate execution time.
All these factors mean that it is literally impossible to predict the execution time of a simple FOR/NEXT loop. You can safely predict that it might complete within 10 seconds, but not to picosecond accuracy. Hence chaotic behaviour.
Three examples exploiting this are the HAVEGE random number generator, the CPU Time Jitter Based Non-Physical True Random Number Generator and the chaotic (but pretty) pictures in Is von Neumann's randomness in sin quote no longer applicable?
-
1$\begingroup$ This answer is deeply flawed in several ways. First, what is non-deterministic in the scenario you describe is not “a software algorithm”, it's the execution of this algorithm on a particular type of hardware. Second, this algorithm uses additional “hidden” inputs, namely the clock values — the mapping of inputs including the sequence of clock values to outputs is still deterministic. $\endgroup$ Commented Dec 7, 2018 at 20:34
-
$\begingroup$ Third, the computers you describe are not the whole world — there are billions of microcontrollers out there with no pipelining, no caches, etc. (Including some in your PC!) Fourth, even on a PC, the clock can be made more deterministic under adversarial conditions, for example by forcing speed throttling and poisoning caches. You may think it's impossible, but that's just a deficiency in your imagination: competent black hats can do this sort of things. $\endgroup$ Commented Dec 7, 2018 at 20:36