Tags

A deterministic process is one you can predict. If I implement a random number generator on a computer (to satisfy the pedants, let’s say it’s a linear congruent one with fixed random seed), I can predict the entire sequence of numbers it spits out if I know the seed and number of numbers pulled off the generator before.

A nondeterministic process is one you cannot. We don’t really know of such a process, because we’re finite creatures yet the potential number of patterns an infinite sequence could follow, yet appear random over finite lengths, is infinite. Let me hand you a sequence of numbers:

05820974944592307816406286208998628034825342117067
98214808651328230664709384460955058223172535940812
84811174502841027019385211055596446229489549303819
64428810975665933446128475648233786783165271201909
14564856692346034861045432664821339360726024914127
37245870066063155881748815209209628292540917153643
67892590360011330530548820466521384146951941511609
43305727036575959195309218611738193261179310511854
80744623799627495673518857527248912279381830119491
29833673362440656643086021394946395224737190702179
86094370277053921717629317675238467481846766940513 …

It goes on indefinitely. You throw every test for randomness you know of at it, and every one passes. You declare it to be random, at which point I reveal it’s actually the digits of π after the first 50. As there are an infinite number of offsets within π I could pick, that alone gives me an infinite amount of infinite sequences.

So there’s no way to prove a process is nondeterministic. We can, however, say that a process is nondeterministic according to our best knowledge, rescuing the concept from Ockham’s Razor by invoking relativism.

But even if we grant nondeterminism exists in the absolute sense, we can still muddy the waters. Suppose I have a process that generates events at nondeterministic times; given an arbitrary amount of information, no-one can predict the precise moment the next event occurs.

However, this process is one-way, with a certain probability of happening at any given time. And as it’s rather inconvenient to carry around one copy of this process at a time, I instead cart around several trillion trillion. Now, however, you can describe my process with a high degree of accuracy. Not only can you give me a good estimate of how many events I’ll see over a given timeframe, you can put precise error bars on that estimate.

Is it nondeterministic, if you can partly determine the outcome? Or is it deterministic, if you partly can’t?