- #1

- 1,569

- 2

## Main Question or Discussion Point

I find the definition of randomnumber at mathworld.wolfram.com rather unsatisfying.

Furthermore, dictionary.com will never help me decide what it means for an infinite sequence of numbers to be random.

I read this article once and I have changed it around a bit and I forget (nor can I find) the article. The rough idea is that a subset of N is random (ie it is a random list of numbers) if there is no (finite) formula corresponding to that set.

{1,1,1,1,...} is not random by this definition. f(n)=1 for all n specifies perfectly each term in this sequence.

Well, I think this might be a bit too model-theoretic for some but for the layperson there is some interesting conclusion involving Tarski's undefinability of truth theorem in arithmetic.

This is response to someone on IIDB named Alf about QM and randomness. Later, I challenge Alf to (1) well-define randomness and (2) prove that anything whatsoever in nature is random by this definition.

Also, I note that the set of tautologies corresponds fairly naturally (via Goedel numbering) to a RANDOM subset of N; thus one could intuitively though probably incorrectly decide that truth is random.

Here goes:

I however do not think rolling dice is random and therefore is at best a model for randomness. It's a rather poor example of something random, as is a pseudo-random number generator. In fact, I would go far as to say that we haven't yet both (1) well defined what randomness is and (2) been able to prove that randomness exists in nature.

It is safe to only consider defining randomness in terms of infinite sequences of numbers (which are functions from N to some set of numbers, N, Q, or R). An infinite sequence models the potentially infinite repetition of an experiment such as rolling a die. For example, {1,2,5,4,3,5,4,6,1,2,2,3,2,6,6,...} is a list of all the realized outcomes of rolling a die repeatedly. Thus I will define randomness for an arbitrary quantifiable event to mean that the sequence of numbers representing it is a list of random numbers where the definition of a set of random numbers follows.

I would define a sequence to be a random set of real (for example) numbers if that set is undefinable in (R,<,+,*). I tried to come up with sites that have a definition of definabliblity in model such as (R,<,+,*) and what I found are

http://plato.stanford.edu/entries/model-theory/ (keyword search for "definable") and

http://planetmath.org/encyclopedia/Definable2.html [Broken] . Essentially, a set of real numbers is random if no formula specifies it. That formula could be said to "predict" what will be in that set and thus an aspect of the inherintly unpredictable nature of randomness is tied into this definition. Another, more intuitive definition of random sequence is that it is random if there is no finite formula for the function that it is (again, sequence is a function from N to R, for example). This entails that if a sequence is random and a formula gives to each N the right output in R then that formula is essentially just as big as N. Likewise, if there is a finite formula for the sequence then the sequence is not random. The sequence {1,1,1,1,1,1,1,1,1,....} is obviously not random: define f(n)=1 for all n. A finite formula.

(I think you'll find the gist of this quite interesting.) Do random sequences exist? Yes and I believe I have a nontrivial example that is quite interesting (even for the layperson). Take the set of all wffs (well formed formulas) in 1st order logic. Encode each formula by a number in the following way (essentially), called the Goedel number for the formula if you want to look it up: assign to each logical symbol si [s sub i] a number ai [a sub i]. Then take the formula and read what symbols appear in that formula and make a finite sequence of numbers (a1,...,an). Then use unique prime factorization, mapping this wff to a natural number, the encoding of the formula, by [formula]:=(p1^a1)*...*(pn^an). Here, given formula, [formula] is a notation for the Goedel number of that formula and pi is the i-th prime number (2,3,5,7,11,...). Thus we have a map from the set of all wffs to N. A unique number (by the uniqueness of prime factorization) comes from all formulas. Now consider the set of all tautologies, properly contained in the set of all wffs. Call this set of wffs T. T' is the set of all Goedel numbers of wffs in T. T is the set of all wffs that are in some sense true; i.e., T is the set of all truths. T' is the set of all of the encodings of all truths. Theorem T' is undefinable in (N,<,+,*). This is the so-called Tarski "undefinability of truth" theorem. The theorem says that if you have a finite formula F (which is redundant for wffs because all wffs are finite), then it is not the case that n e T' iff F(n) is true.

Now consider a sequence of all Goedel numbers of all tautologies. I don't care what order the tautologies are in though it is possible to list them all because the whole set of wffs is countable. Thus 316 might be the first number in this sequence where 316 is the Goedel number if some tautology (e.g., for all x, x=x). The second number might be 847826 which the Goedel number of some other tautology. So you have this sequence of Goedel numbers of all the tautologies. This sequence is random.

Thus one could pull a stunt and say truth is random. I wouldn't go that far because I've only made a statement about arithmetic. But "truth is random" is on some superficial intuitive level the conclusion; i.e., the set of all true statements is not definable; i.e., the set of all true statements is not predicatble by some finite formula.

There certainly are a bunch of tautologies so this is a genuine example of randomness.

I think I have well-defined randomness. What your burden is now is to prove that anything in nature corresponds to this or any well-defined notion of randomness.

Note that saying electon behavior is given by some probability distribution is not sufficient to prove randomness of said behavior. {(heads,.5),(tails,.5)} is a probability distribution but as we've seen, rolling a die is NOT random (it is chaotic).

Furthermore, dictionary.com will never help me decide what it means for an infinite sequence of numbers to be random.

I read this article once and I have changed it around a bit and I forget (nor can I find) the article. The rough idea is that a subset of N is random (ie it is a random list of numbers) if there is no (finite) formula corresponding to that set.

{1,1,1,1,...} is not random by this definition. f(n)=1 for all n specifies perfectly each term in this sequence.

Well, I think this might be a bit too model-theoretic for some but for the layperson there is some interesting conclusion involving Tarski's undefinability of truth theorem in arithmetic.

This is response to someone on IIDB named Alf about QM and randomness. Later, I challenge Alf to (1) well-define randomness and (2) prove that anything whatsoever in nature is random by this definition.

Also, I note that the set of tautologies corresponds fairly naturally (via Goedel numbering) to a RANDOM subset of N; thus one could intuitively though probably incorrectly decide that truth is random.

Here goes:

I however do not think rolling dice is random and therefore is at best a model for randomness. It's a rather poor example of something random, as is a pseudo-random number generator. In fact, I would go far as to say that we haven't yet both (1) well defined what randomness is and (2) been able to prove that randomness exists in nature.

It is safe to only consider defining randomness in terms of infinite sequences of numbers (which are functions from N to some set of numbers, N, Q, or R). An infinite sequence models the potentially infinite repetition of an experiment such as rolling a die. For example, {1,2,5,4,3,5,4,6,1,2,2,3,2,6,6,...} is a list of all the realized outcomes of rolling a die repeatedly. Thus I will define randomness for an arbitrary quantifiable event to mean that the sequence of numbers representing it is a list of random numbers where the definition of a set of random numbers follows.

I would define a sequence to be a random set of real (for example) numbers if that set is undefinable in (R,<,+,*). I tried to come up with sites that have a definition of definabliblity in model such as (R,<,+,*) and what I found are

http://plato.stanford.edu/entries/model-theory/ (keyword search for "definable") and

http://planetmath.org/encyclopedia/Definable2.html [Broken] . Essentially, a set of real numbers is random if no formula specifies it. That formula could be said to "predict" what will be in that set and thus an aspect of the inherintly unpredictable nature of randomness is tied into this definition. Another, more intuitive definition of random sequence is that it is random if there is no finite formula for the function that it is (again, sequence is a function from N to R, for example). This entails that if a sequence is random and a formula gives to each N the right output in R then that formula is essentially just as big as N. Likewise, if there is a finite formula for the sequence then the sequence is not random. The sequence {1,1,1,1,1,1,1,1,1,....} is obviously not random: define f(n)=1 for all n. A finite formula.

(I think you'll find the gist of this quite interesting.) Do random sequences exist? Yes and I believe I have a nontrivial example that is quite interesting (even for the layperson). Take the set of all wffs (well formed formulas) in 1st order logic. Encode each formula by a number in the following way (essentially), called the Goedel number for the formula if you want to look it up: assign to each logical symbol si [s sub i] a number ai [a sub i]. Then take the formula and read what symbols appear in that formula and make a finite sequence of numbers (a1,...,an). Then use unique prime factorization, mapping this wff to a natural number, the encoding of the formula, by [formula]:=(p1^a1)*...*(pn^an). Here, given formula, [formula] is a notation for the Goedel number of that formula and pi is the i-th prime number (2,3,5,7,11,...). Thus we have a map from the set of all wffs to N. A unique number (by the uniqueness of prime factorization) comes from all formulas. Now consider the set of all tautologies, properly contained in the set of all wffs. Call this set of wffs T. T' is the set of all Goedel numbers of wffs in T. T is the set of all wffs that are in some sense true; i.e., T is the set of all truths. T' is the set of all of the encodings of all truths. Theorem T' is undefinable in (N,<,+,*). This is the so-called Tarski "undefinability of truth" theorem. The theorem says that if you have a finite formula F (which is redundant for wffs because all wffs are finite), then it is not the case that n e T' iff F(n) is true.

Now consider a sequence of all Goedel numbers of all tautologies. I don't care what order the tautologies are in though it is possible to list them all because the whole set of wffs is countable. Thus 316 might be the first number in this sequence where 316 is the Goedel number if some tautology (e.g., for all x, x=x). The second number might be 847826 which the Goedel number of some other tautology. So you have this sequence of Goedel numbers of all the tautologies. This sequence is random.

Thus one could pull a stunt and say truth is random. I wouldn't go that far because I've only made a statement about arithmetic. But "truth is random" is on some superficial intuitive level the conclusion; i.e., the set of all true statements is not definable; i.e., the set of all true statements is not predicatble by some finite formula.

There certainly are a bunch of tautologies so this is a genuine example of randomness.

I think I have well-defined randomness. What your burden is now is to prove that anything in nature corresponds to this or any well-defined notion of randomness.

Note that saying electon behavior is given by some probability distribution is not sufficient to prove randomness of said behavior. {(heads,.5),(tails,.5)} is a probability distribution but as we've seen, rolling a die is NOT random (it is chaotic).

Last edited by a moderator: