Hacker News Reader

Comment by ttctciyf | Hacker News Reader

The author alludes to the fact that the overwhelming majority of reals have an infinite number of decimal places that constitute an algorithmically random sequence[1]

Sure, plenty of real numbers have finite (0.1, 0.01, ...) or non-random (0.111..., 0.0111..., ...) sequences of decimal places, but there are only a countable infinity of these, whereas there is an uncountable infinity of the other, "random," kind.

Usually we almost exclusively deal in the only-countably-infinite subset of the reals which are not random and it's counterintuitive that these comprise a tiny tiny archipelago of order in a huge engulfing ocean of randomness, but such is the case.

Gregory Chaitin's "How real are real numbers?"[2] has some relatively straightforward further reading on this if you're interested.

1: https://en.wikipedia.org/wiki/Algorithmically_random_sequenc...

2: https://arxiv.org/abs/math/0411418

View on HN

The author's writing has a lot of background behind it that is true and yet the author's argument that they should be called "random numbers" is poor, at best. It is not typically helpful to think of real numbers that way - at the very least you're "missing" a tiny but hugely important subset that aren't random in any sense. But more importantly, it doesn't match up with any of the usual definitions of real numbers since those involve no such restrictions of randomness of digit expansions (and generally avoid digit expansions entirely). We might as well argue that the real numbers aught to be called the non-zero numbers since almost every one of them is non-zero.

I don't think the author seems particularly aware of the existence of such arguments in the past (I assume he comes from a physics background and is new to this - though so am I). Glancing through the works cited I don't see references to past treatments of this idea like Chaitin's. If the author is not a crank, he is doing a poor job of convincing us of it.

Chaitin is a serious scientist/mathematician who knows what he is talking about, and there is plenty of discussion to other works and references in his own research. And his published work on algorithmic information theory is quite extensive.

He is using the notion of randomness as "uncompressibility", which is a very mainstream view (perhaps better known as Kolmogorov complexity, who is much more well known than Chaitin).

Just because you are not convinced doesn't mean he's a crank, it just means your background in this area is limited.

I would also note that you're reading a popular text, one that is purposefully designed to reach a mass audience, so the lack of formalism is likewise intentional, and not a reflection of crankism. You're welcome to look up his research papers if you'd like to see the difference.

I think you misread my comment which was not at all commenting on Chaitin! I was commenting on the article by Gisin, the one this thread is on.

He's a very reputable theoretical quantum physicist with several respectable results to his name. I know because my PhD was in a similar field. You could perhaps accuse him of ignorance of results in other specialities, but not crankism.

Not necessarily. Linus Pauling had several respectable results to his name, too. Even the smartest people can be so wrong when working in fields even a little bit outside their specialism that they are almost indistinguishable from cranks.

This IS his field of research.

I only accused the author of doing a bad job of not looking like a crank. I realize that non-cranks do that sometimes.

I don't know if it's still the case, but arxiv papers without a subject classifier used to be more likely to be "cranky" (contrast the /math/ in the Chaitin paper url.)

So I don't know about the paper here - I only read the abstract - but I wouldn't get too hung up on terminology. "Random" is just an easier way of saying "uncomputable" I guess. But the broad topic itself is quite respectable and of interest to non-cranks, for example, see John Baez' "Struggles with the Continuum"[1]:

> Is spacetime really a continuum, with points being described — at least locally — by lists of real numbers? Or is this description, though immensely successful so far, just an approximation that breaks down at short distances? Rather than trying to answer this hard question, let us look back at the struggles with the continuum that mathematicians and physicists have had so far....

1: http://math.ucr.edu/home/baez/continuum.pdf

EDIT: The author seems like a perfectly respectable, non-crank physicist (https://en.wikipedia.org/wiki/Nicolas_Gisin) as per another comment here.

That difference is due to a systematic change in how arXiv generates URLs for submissions, starting a few years ago. No arXiv submissions today will have a URL with a category. Articles (each with a unique arXiv id YYMM.xxxxx) can have multiple topic tags; the article under discussion has two tags, one of which is "quant-ph". Cranky articles which cannot be refuted on technical grounds are often found on the "general" topic tags.

As an aside, since the above comment is essentially trying to infer the quality of the paper from metadata, it might be worth knowing that the author is a well-regarded quantum physicist with many highly cited papers.

Nitpick: non-random numbers are rare (this word is usually formalized as "the set of all non-random numbers has measure zero"), but still uncountable. The set of computable sequences is countable, but it is only a tiny subset of non-random sequences. For example, 0.0x₁0x₂… is non-random (= partially predictable) for any sequence x₁x₂…, and this set is obviously non-countable.

I think sets like 0.0x₁0x₂… ought to be considered "mixed random", not "non-random", since they are homomorphic to a superset of random numbers. (My terminology is hand-wavy.)

Is this a difference between random and algorithmically random? I'd have expected "not computable" to be synonymous with "algorithmically random."

Could you show us one of these "random" reals?

There is a simple algorithm for generating every possible decimal number:

  x.0
  x.1
  x.2
  ...
  x.01
  x.02
  ...
  x.10
  x.11
  x.12
  ...
  x.20
  x.21
  ...
  x.30
  x.31
  ...
  x.99
  x.001
  x.002
  ...

In binary, it's even simpler; you just generate every permutation of bits.

Your proposed enumeration of decimals (counter-intuitively) would miss an uncountably infinite number of values. This enumeration is not possible in any fashion, which you can prove fairly easily with Cantor's Diagonal Argument[1].

The punch-line is that there are more real numbers between 0 and 1 than there are whole numbers greater than 0. The proof basically shows that even if you imagine that you had a countably-infinitely-long list of all the real numbers between 0 and 1, you can construct a number that must be missing from the list -- which is a contradiction, and thus no such list can exist (implying that there are more numbers between 0 and 1 than numbers greater than 0).

For instance, your enumeration is missing every irrational (or even recurring decimal) number. That set of numbers is uncountably infinite.

[1]: https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

>The proof basically shows that even if you imagine that you had a countably-infinitely-long list of all the real numbers between 0 and 1, you can construct a number that must be missing from the list -- which is a contradiction, and thus no such list can exist (implying that there are more numbers between 0 and 1 than numbers greater than 0).

So, there is no list of all the real numbers between 0 and 1, but you are claiming there are uncountably infinite of them?

That's the definition of uncountably infinite: can not be put in 1-to-1 correspondence with the integers (can not be listed).

Yes, because if there were such a list then you could assign a 1-to-1 mapping (by list index) of each number between 0 and 1 to a whole number which would prove they have the same size. If it is impossible to have a complete list of all real numbers between 0 and 1 then there cannot be such a mapping, and thus you'll "run out" of integers before you've counted all of the reals (more correctly you're showing that the size must be larger because if it was smaller or of equal size it could fit in such a list).

Numberphile did a pretty good introductory video to this if you want to learn more: https://www.youtube.com/watch?v=elvOZm0d4H0.

That is pretty much the definition of uncountability :)

It's counter-intuitive, but your algorithm actually only generate a subset of the rational numbers. That's because all of your numbers have a finite number of decimal digits. Most reals, like 1/3 or pi, will never appear in your list. (Though numbers close to them will.)

Most reals don't have a generating algorithm, since there is an uncountable number of reals, but only a countable number of algorithms. (Assuming an algorithm has to be a finite length program.)

I'm not sure 1/3 is exactly a number. It seems to be an expression when written out. pi, likewise, appears to be a word, not a number.

Numbers aren't lists of digits. They're abstract concepts that are referred to by lists of digits for the purpose of convenience. You can even have numbers without having invented digits. It's just annoying to write out one million, two hundred thirty-four thousand, five hundred sixty-seven and eighty-nine hundredths. So, we say 1,234,567.89 (or 1.234.567,89 for countries that use the comma for decimals).

0.5 in base 10 is the same as 0.1 in base 2, which is the same as 0.11111... in base 3. And the choice of base is completely arbitrary, with some societies using others, like base 12 or base 60.

That gives every terminating decimal or binary number. For example, you will never list 1/3, or pi or sqrt(2).

To see why you cannot generate every possible real number as a list, look up cantors diagonal argument.

Are you sure 1/3 is a real number?

Real numbers are defined as a particular extension of the rational numbers, which 1/3 is.

"Real numbers" here refers to a very specific construction of numbers. There is pretty good argument, which the actual post is about, that states this construction is actually rather unrealistic.

The issue being that there are way to many "real numbers".

It's as "real" as 1/2, which is on your list.

I guess you also need to interpret each number in the list in each possible base.

I'll be generous and assume you mean decimal as in the data-type: an interesting set of "floating point" numbers that behaves really badly (not a field, for example)

Reply on news.ycombinator.com