Can a truly random number be constructed?

[PeroK]

Here's a challenge of sorts, inspired by some previous discussions.

You must choose a random number uniformly on the interval $[0, 1]$. If the number is rational, someone wins a £1 million prize. If the number is irrational, no prize is won.

It is your task to devise the method by which the random number is chosen and checked for rationality. All numbers between $0$ and $1$ must have an equal probability (density) of being chosen.

What we know from probability theory is that the probability of a rational number being chosen is 0, but that it is still "possible", in some sense.

My belief is that the challenge is impossible, although I am happy to be proved wrong.

 

[Buzz Bloom]

Hi PeroK:

I think there are some conceptual issues with your question.

(1) How do you define "select a random number?
(2) How is the selected random number identified so that it can be tested for whether of not is is rational?

There are likely to be other conceptual issues which depend on how you answer these two questions.

Regards,
Buzz

 

[PeroK]

Hi PeroK:

I think there are some conceptual issues with your question.

(1) How do you define "select a random number?
(2) How is the selected random number identified so that it can be tested for whether of not is is rational?

There are likely to be other conceptual issues which depend on how you answer these two questions.

Regards,
Buzz

(1) and (2) are what the method has to establish. I don't really see any conceptual issues. I see practical issues.

 

[AplanisTophet]

The "odds" of chosing a rational in this case are, to the best we are able to (currently) define, 0, however, the irrationals can be mapped uniformly to the rationals, so if the contest allows for the selection of a rational by

1) randomly selecting it, or
2) randomly selecting a rational equal to f(x) where f is a uniform mapping of the irrationals in [0, 1] to the rationals in [0, 1],

then I suppose it could be done.

Now, I assume people will say, "hey, there is no uniform mapping of the irrationals on [0, 1] to the rationals on [0, 1]." To that, I say see https://www.physicsforums.com/threads/selecting-a-natural-and-a-real-uniformly-at-random.911544/

I'm looking for clarification myself.

 

[Buzz Bloom]

Hi

(1) and (2) are what the method has to establish. I don't really see any conceptual issues. I see practical issues.

Hi PeroK:

Just for the sake of discussion I assert that there is NO practical way to "select a random number" from the set of reals, say limited to reals between zero and one.
Do you dispute that? If so, what argument, if any, do you offer?

Regards,
Buzz

 

[AplanisTophet]

Hi

Hi PeroK:

Just for the sake of discussion I assert that there is NO practical way to "select a random number" from the set of reals, say limited to reals between zero and one.
Do you dispute that? If so, what argument, if any, do you offer?

Regards,
Buzz

Great point.

My take is that if we want to assert both the axiom of infinity (implying the existence of the natural numbers) and our ability to flip a coin (function $f$), then we should be able to assert the existence of an infinite binary sequence $S = s_1, s_2, s_3, …$ where each element of the sequence is selected randomly: $f(n) = s_n$.

 

[PeroK]

Hi

Hi PeroK:

Just for the sake of discussion I assert that there is NO practical way to "select a random number" from the set of reals, say limited to reals between zero and one.
Do you dispute that? If so, what argument, if any, do you offer?

Regards,
Buzz

I agree with that. I think even (1) is impossible. But, in another thread, we have a suggestion to use a dartboard.

I think that "let X be a random variable distributed uniformly on [0,1]" makes sense mathematically. But, I'm not convinced that it can be applied to reality. The Internet is full of (attempted) serious applications of probability theory that involve choosing a random number like this. But, if you can't actually do it, then it's meaningless. You have to remain in the abstract realm of mathematics.

 

[TeethWhitener]

My belief is that the challenge is impossible

I'm guessing that determining whether a random number $\in [0,1]$ is rational or irrational will end up being equivalent to the halting problem, and therefore undecidable. "Is it rational?" is basically "Does it halt or repeat?" which is pretty close to "Does it halt?" in my book.

 

[PeroK]

I'm guessing that determining whether a random number $\in [0,1]$ is rational or irrational will end up being equivalent to the halting problem, and therefore undecidable. "Is it rational?" is basically "Does it halt or repeat?" which is pretty close to "Does it halt?" in my book.

Yes, after I posted the question, I began to wonder about that too.

 

[TeethWhitener]

Yes, after I posted the question, I began to wonder about that too.

In fact, I'm almost certain it is: a number $n \in [0,1]$ is rational iff $nk \in \mathbb{N}$ for some natural number $k$. A test for rationality would be equivalent to:

Multiply n by k
  if n*k is a whole number then
    halt
  else
    k = k++

This is pretty much the exact setup for the halting problem.

 

[AplanisTophet]

In fact, I'm almost certain it is: a number $n \in [0,1]$ is rational iff $nk \in \mathbb{N}$ for some natural number $k$. A test for rationality would be equivalent to:

Multiply n by k
  if n*k is a whole number then
    halt
  else
    k = k++

This is pretty much the exact setup for the halting problem.

Every rational will have a finite expansion in some base (e.g., dyadic rationals have a finite binary expansion).

Without a finite expansion, I don't see how a computer could even compute n*k much less get to the k++ part, as long as we're being "practical." By the time you know whether the number has a finite expansion in some base, you have your answer.

Is checking whether the number has a finite expansion in some base equivalent to the halting problem too?

 

[SlowThinker]

It is your task to devise the method by which the random number is chosen and checked for rationality. All numbers between $0$ and $1$ must have an equal probability (density) of being chosen.

The true challenge here is, how do I tell you which number I selected? Most of them, 100%, require infinite amount of information to be described.

 

[SSequence]

I'm guessing that determining whether a random number $\in [0,1]$ is rational or irrational will end up being equivalent to the halting problem, and therefore undecidable. "Is it rational?" is basically "Does it halt or repeat?" which is pretty close to "Does it halt?" in my book.

There is a straight-forward mapping (total and onto but not 1-1) from the set N to the set of all reals with computable decimal representations. Here is how it goes. For example, first treat the given input (say x) as an index to a program. Assume a 1-1 correspondence between N and the set of programs (which should be easy to establish) ... or at least an onto mapping. Denote the function computed (by program with index x) as f: N→N. Now if for example we had:
f(0)=15, f(1)=10, f(2)=12, f(3)=14, f(4)=6 ...
convert it to:
g(0)=15, g(1)=10%10=0, g(2)=12%10=2, g(3)=14%10=4, g(4)=6%10=6,...
So the corresponding real number is:
15.0246...

What if the function f computed by the program was partial? Well in that case we can assume a string of 0's starting from the smallest point from which f was partial. For example, in the above case if f(5) was undefined/partial then the corresponding real number would be:
15.02460000000000...

Now one can ask that whether it is decidable/recursive whether when we select a given number as input, can we decide whether the real that the input selection is supposed to represent is rational or not. By rice's theorem the answer is no (demonstrated by giving simple example of two separate programs, one whose function corresponds to some rational number and one whose function corresponds to some irrational number).

==========

But the actual question is of selecting an arbitrary real. Now taking the point of real numbers as uncountable, by the very definition we have no correspondence function from N to the reals. But I think that one may perhaps set certain properties that would hold after finite number of arbitrary selections as such. Don't know how useful it would be though.

 

[Stephen Tashi]

The true challenge here is, how do I tell you which number I selected? Most of them, 100%, require infinite amount of information to be described.

How are we measuring "information"? $\$ Is "$\sqrt{2}$" an infinite amount of information?

 

[TeethWhitener]

@SlowThinker and @SSequence bring up an important point, namely that the computable numbers are countable. It might be more interesting to restrict one's attention to the set of computable numbers between 0 and 1. Is there an efficient algorithm to determine, from this restricted set, whether a given number is rational or irrational? I honestly have no idea.

 

[Stephen Tashi]

I think that "let X be a random variable distributed uniformly on [0,1]" makes sense mathematically. But, I'm not convinced that it can be applied to reality. The Internet is full of (attempted) serious applications of probability theory that involve choosing a random number like this. But, if you can't actually do it, then it's meaningless. You have to remain in the abstract realm of mathematics.

A mathematical model like "let X be a random variable distributed uniformly on [0,1]" could be useful even if it is physically impossible to implement. It could be useful as an approximation to situations that are physically possible.

I'm not sure that it is physically possible to select a random number from a uniform discrete distribution on {1,2,...9, 10}, but let's assume it is. We could use that process to approximate sampling from a uniform distribution on [0,1] to a given "granularity" in stages by picking one of 10 equal length subintervals of [0,1] and then picking a sub-subinterval of that subinterval etc.

Suppose we have a problem, whose answer $A(\epsilon)$ is a function of $\epsilon$, the smallest length interval we use. We can define a "limiting answer" as $A = \lim_{\epsilon \rightarrow 0} A(\epsilon)$ when such a limit exists.

It may be that the answer $A$ can be computed by manipulations involving the assumption that we take samples from a uniform distribution on [0,1] instead by computing the answer for a finite $\epsilon$ and then taking a limit. In such a situation, the practical value of using the continuous model depends first on whether the "limiting answer" $A$ has any practical significance and second on whether the manipulations using the uniform distribution simplify calculations.

My first impression is that theoretical questions like "What is the probability that a number selected from a uniform distribution on [0,1] is an irrational number?" can't be formulated as a "limiting answer" to a sequence of finite approximations. But less theoretical questions like "What is the distribution of the mean of N samples from a uniform distribution on [0,1] ?" could be.

 

[AplanisTophet]

How are we measuring "information"? $\$ Is "$\sqrt{2}$" an infinite amount of information?

@SlowThinker and @SSequence bring up an important point, namely that the computable numbers are countable. It might be more interesting to restrict one's attention to the set of computable numbers between 0 and 1. Is there an efficient algorithm to determine, from this restricted set, whether a given number is rational or irrational? I honestly have no idea.

"Odds" are, we're talking about an infinitely long string of numbers in any base. Yeah, it's abstract and theoretical in most every sense of those terms. Focusing on computable numbers only is off topic and trying to assert that a computer could determine after a finite number of steps whether the number repeats or terminates in any base 'every time' so as to avoid the halting problem is just not going to happen.

If a computer can load the number into its memory so to speak in any given base, then just as you give a mouse a cookie it can in any base, so we're done. A finite expansion in any base means it's rational and if none exists, it's not. Yeah, the halting problem could easily be asserted here as "practically" (not sure the mathematical context of that word) we can't wait around to see if our computer program halts or not. We're done. You either have to acknowledge a trip into the theoretical like a mathematician or stick to reality like a physicist (pardon my rudeness please), your choice.

 

[TeethWhitener]

"Odds" are, we're talking about an infinitely long string of numbers in any base. Yeah, it's abstract and theoretical in most every sense of those terms. Focusing on computable numbers only is off topic and trying to assert that a computer could determine after a finite number of steps whether the number repeats or terminates in any base 'every time' so as to avoid the halting problem is just not going to happen.

If a computer can load the number into its memory so to speak in any given base, then just as you give a mouse a cookie it can in any base, so we're done. A finite expansion in any base means it's rational and if none exists, it's not. Yeah, the halting problem could easily be asserted here as "practically" (not sure the mathematical context of that word) we can't wait around to see if our computer program halts or not. We're done. You either have to acknowledge a trip into the theoretical like a mathematician or stick to reality like a physicist (pardon my rudeness please), your choice.

"Computable" in this context has a precise mathematical definition. It's not based on whether an actual physical computer can store it in memory.
https://en.m.wikipedia.org/wiki/Computable_number

 

[Stephen Tashi]

A finite expansion in any base means it's rational and if none exists, it's not.

In base 10, the infinite expansion 0.333... is a rational number.

One could use $\sqrt{2}$ as the base and express some irrational numbers as finite expansions.

 

[AplanisTophet]

"Computable" in this context has a precise mathematical definition. It's not based on whether an actual physical computer can store it in memory.
https://en.m.wikipedia.org/wiki/Computable_number

Yes, but the OP was to select a number randomly in [0,1], not a computable number.

 

[AplanisTophet]

In base 10, the infinite expansion 0.333... is a rational number.

One could use $\sqrt{2}$ as the base and express some irrational numbers as finite expansions.

Yes, but in base 3 it's got a finite expansion. No need for 'infinite' memory as is the case with all rationals.

The OP is to find a rational, not some number in an irrational base.

 

[SSequence]

@SlowThinker and @SSequence bring up an important point, namely that the computable numbers are countable. It might be more interesting to restrict one's attention to the set of computable numbers between 0 and 1. Is there an efficient algorithm to determine, from this restricted set, whether a given number is rational or irrational? I honestly have no idea.

As I described in the previous post, that under a reasonable (total and onto) mapping from N to reals with computable decimal representations, the problem is not decidable/recursive.
Here a reasonable mapping means that you can write a simple program so that given any number as input, the program determines the corresponding real to arbitrary precision (in sequential/non-terminating sense).

There is also a somewhat related but separate problem. You could be given a program/function f as a blackbox essentially and "already" told that its total. Then your task is to determine whether it represents a rational or not. But I think that it would be extremely likely (though I haven't tried to look at the reasoning) that this is not amenable to any uniform algorithm (in terms of the given function f) either.

But seemingly, non-recursive sets don't necessarily preclude a notion of probability. I think this would become a little context dependent then probably. The following might be of some interest (I happened to have glanced it few years ago but haven't really read it):
https://projecteuclid.org/euclid.ndjfl/1168352664
Looking very briefly, I think the part about probability of FIN is probably relevant here (page 6 of 10).

==========

Also I think there is a general issue with how to make an "unpredictable" selection. If someone told you to make a selection (based upon a fixed indexing such as above) and the selection program always started from 0 fresh, the selection would hardly be unpredictable. If however, the program kept/stored a counter and never resetted it (instead only incremented it) then it would be different.

 

[PeroK]

Thanks to everyone who replied. As I suspected, the challenge as stated is not practical and perhaps for more reasons that I originally anticipated.

 

[sysprog]

There is no atomic distance on a numeric interval, except by definition the infinitesimal.

When we try to select a number from within the interval from 0 to 1 at random, we cannot determine what number we have selected, unless it is numerically determinate, and therefore not irrational.

If our selection is proving to be non-determinate, we cannot legitimately be said to have selected a number, unless we have a non-numeric name for some irrational part of the number as specified, e.g. Φ/5 would be an irrational number within the interval.

If only rational numbers can be definitively selected, the selection is 100% non-random vis-a-vis rational vs irrational.

If our set of choices is allowed to include a named irrational number, e.g. Φ, divided by a rational number > Φ so as to keep the result within the interval, we could choose a qualified rational number X at random, then choose at random with 50% probability whether to divide Φ by it or instead divide it by another rational number chosen at random from numbers > X so that the resulting fraction would be within the interval, and would be a random number with equal probability of being a rational or irrational number ...

 

[FactChecker]

There is no atomic distance on a numeric interval, except by definition the infinitesimal.

When we try to select a number from within the interval from 0 to 1 at random, we cannot determine what number we have selected, unless it is determinate, and therefore not irrational.

If our selection is proving to be non-determinate, we cannot legitimately be said to have selected a number,

A number can be selected without giving it a name. There is a significant difference between selecting a number and naming or even identifying it. If it exists, it can be selected.

 

[sysprog]

A number can be selected without giving it a name. There is a significant difference between selecting a number and naming or even identifying it. If it exists, it can be selected.

Selection of a number cannot meaningfully be said to have occurred if the number selected cannot be somehow designated or described. If someone claims to have selected a number, he should, having done so, be able to somehow identify the selection, or it is not meaningful to call it the selected number. If someone says he has selected "that number the square of which is exactly 1 greater than itself" he has thereby "named" i.e. specified, the number Φ. He cannot state the infinite decimal expansion of an irrational number. To accurately and informatively report the selection of of an irrational number, one must state some conventional name for it or use a functional description or other uniquely identifying characteristic set to identify it, i.e. name it.

 

[FactChecker]

Selection of a number cannot meaningfully be said to have occurred if the number selected cannot be somehow designated or described. If someone claims to have selected a number, he should, having done so, be able to somehow identify the selection, or it is not meaningful to call it the selected number. If someone says he has selected "that number the square of which is exactly 1 greater than itself" he has thereby "named" i.e. specified, the number Φ. He cannot state the infinite decimal expansion of an irrational number. To accurately and informatively report the selection of of an irrational number, one must state some conventional name for it or use a functional description or other uniquely identifying characteristic set to identify it, i.e. name it.

I should have been more careful with my words. The words "select" and "designate" are really synonyms, so I shouldn't have said "designate". A process can select a number even if no one can name it or right down all it's digits. If it exists, it can be selected.
We should distinguish between the concepts of selecting a number versus recording the selected number in some human understandable way. They are not the same.

 

[SSequence]

...
When we try to select a number from within the interval from 0 to 1 at random, we cannot determine what number we have selected, unless it is numerically determinate, and therefore not irrational.
...

There are number of factors here.

For example, see post#13 where I described a total and onto mapping from the set N to the set of all reals with computable decimal representations (of course the simple trick is simply choosing the expansion of 0's from the first point a partial recursive function becomes partial). Also, as I described in post#22 the mapping has the property that you can write a simple program so that given any number as input, the program determines the corresponding real to arbitrary precision.
You could also do something quite similar with rationals. For example, with a simple pairing function (such as ones used in simple cardinality arguments to show rationals are countable) we have a total and onto mapping from N to the rationals.

However, there is an important difference between the two in a sense. In the latter case given the indexes representing any two rationals, the following functions are computable/recursive:
equal: N²→{0,1}
greater: N²→{0,1}
As an example suppose(hypothetically) the two indexes (as a random example say 10 and 15) that were picked represented the rational numbers 2/4 and 4/8 respectively. In that case we will have:
equal(10,15)=1 (true)
greater(10,15)=0 (false)
It can be seen easily that both the above functions are computable here. For example, to calculate equal all that has to be done is reduce both of rationals is to reduced fractional form (until it isn't possible to simplify anymore).
Of course because the function "equal" is computable, we can (with relative ease) describe 1-1 correspondence between the set N and the rational numbers (while of course also being able to write a simple program to calculate the values to arbitrary decimal places when given an index as input).

In the former case however (reals with computable decimal representations), the functions equal and greater wouldn't be computable. It would take a little bit of (somewhat elementary) work to show it (unless one directly uses some general result), but nevertheless, it isn't difficult to show that.

 

[sysprog]

I should have been more careful with my words. The words "select" and "designate" are really synonyms, so I shouldn't have said "designate". A process can select a number even if no one can name it or right down all it's digits. If it exists, it can be selected.

In the case of a not-observably-deterministic process, if the process can and does apparently randomly select a number, some state of affairs will be different after the selection occurs from what it was prior to the selection having occurred, and some set of aspects of the overall change set must have a correspondence unique to the number selected. For the selection to be meaning qua selection, interrogability of that set of aspects sufficiently to indicate the identity of the number selected is necessary.

.
We should distinguish between the concepts of selecting a number versus recording the selected number in some human understandable way. They are not the same.

Selection is meaningless if the difference between one selection and another is opaque.

 

[sysprog]

There are number of factors here.

For example, see post#13 where I described a total and onto mapping from the set N to the set of all reals with computable decimal representations (of course the simple trick is simply choosing the expansion of 0's from the first point a partial recursive function becomes partial). Also, as I described in post#22 the mapping has the property that you can write a simple program so that given any number as input, the program determines the corresponding real to arbitrary precision.

The inquiry did not seek the designation of irrationals "to arbitrary precision", which is why in focusing on them, I remarked regarding their being choosable only by names or by function description or designation.

You could also do something quite similar with rationals. For example, with a simple pairing function (such as ones used in simple cardinality arguments to show rationals are countable) we have a total and onto mapping from N to the rationals.

The formal insolubility of the halting problem does not stop loop detectors from with a high degree of accuracy alerting programmers to egregious behavior indicative of high probability that a suspect program will not halt.

However, there is an important difference between the two in a sense. In the latter case given the indexes representing any two rationals, the following functions are computable/recursive:
equal: N²→{0,1}
greater: N²→{0,1}
As an example suppose(hypothetically) the two indexes (as a random example say 10 and 15) that were picked represented the rational numbers 2/4 and 4/8 respectively. In that case we will have:
equal(10,15)=1 (true)
greater(10,15)=0 (false)
It can be seen easily that both the above functions are computable here. For example, to calculate equal all that has to be done is reduce both of rationals is to reduced fractional form (until it isn't possible to simplify anymore).
Of course because the function "equal" is computable, we can (with relative ease) describe 1-1 correspondence between the set N and the rational numbers (while of course also being able to write a simple program to calculate the values to arbitrary decimal places when given an index as input).

In the former case however (reals with computable decimal representations), the functions equal and greater wouldn't be computable. It would take a little bit of (somewhat elementary) work to show it (unless one directly uses some general result), but nevertheless, it isn't difficult to show that.

For irrationals, how much greater would not be computable, but whether greater would be, and for equals, it would be possible to determine whether the generating function, if deterministic, was equivalent. The results of applying processing capacity to the production of numerical approximations of stochastic differential and partial differential equations, while for many purposes worthily applicable, are not definitive selections of numbers as specified in the topic postulation of this discussion. As a practical matter, it is often easy to determine with certainty that a rational number is rational, and often elusive to determine that a generating function is selecting an irrational number, and if so which one, and how it can be perspicuously, or at least useably for the intended purpose, designated.

 

[SSequence]

I can't quite follow your post.

What I was simply saying was that:
IF you have a mapping (total and onto) from N to some subset of real numbers such that given any index you have a program that can calculate*** the corresponding number to arbitrary precision.
THEN it doesn't automatically follow that the corresponding functions "equal" and "greater" are computable (they may or may not be).

Now even though the conclusion doesn't always happen from the premise, for rational numbers both of them happen to be true. However, the rational numbers are certainly not the only subset (of reals) for which both the premise and conclusion above are true. In fact, one can easily describe proper super-sets of rational numbers for which both the premise and conclusion above are true (so at least in that specific sense there is nothing special about rational numbers). This is simply what I was trying to say.*** One can formally create (without much trouble) a further distinction that would disallow somewhat artificial mapping of post#13. I haven't assumed that in the premise here though (so even the artificial mapping of post#13 is allowed).
However, an interesting question would be that if one did disallow artificial mappings(such as mentioned) then can one show that implication described in this post would always hold or it could fail (this possibly might be a more difficult question than it looks)? I haven't thought about that, but it is a bit besides the main point though.

 

[FactChecker]

Selection is meaningless if the difference between one selection and another is opaque.

So many posts are talking about the inability to determine or record an infinite number of digits. That is irrelevant. A physical process can "select" an exact position in space without any human recording or determining that exact position.

 

[Buzz Bloom]

We should distinguish between the concepts of selecting a number versus recording the selected number in some human understandable way. They are not the same.

Hi FactChecker:

Yes, they are conceptually not the same, but so far in this thread these concepts remain undefined. For example, is selection a process? If so, does it require a description of how the process works? Does the process have to complete in a finite time?

Here is a simpler question. How do you define a process for selecting a random positive integer such that each integer has the same probability of being selected as any other integer?

Regards,
Buzz

 

[Buzz Bloom]

Now, I assume people will say, "hey, there is no uniform mapping of the irrationals on [0, 1] to the rationals on [0, 1]." To that, I say see https://www.physicsforums.com/threads/selecting-a-natural-and-a-real-uniformly-at-random.911544/

Hi Aplanis:

If you are using the axiom of choice then perhaps you might want to consider that it is a mathematical axiom rather than a description of a process that is possible to implement in a practical manner in the real world.

Regards,
Buzz

 

[PeroK]

So many posts are talking about the inability to determine or record an infinite number of digits. That is irrelevant. A physical process can "select" an exact position in space without any human recording or determining that exact position.

The original challenge in post #1 was to do something with the selected number.

The implication of your theory about space is that the uncountable infinity of the reals must exist in reality. That may be so, but equally it may not be so.

Not least, because if you believe QM, you cannot point at a particle and say that the position of that particle at a specified instant defines a single real number.

The conclusion of this thread, I believe, is that real numbers can be conjured mathematically, but not by any physical process.