Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Connections in Math: the two kinds of random

stillthinking.net

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Connections in Math: the two kinds of random

#21

Post by hahahaa »

zzless wrote: post #10

The choice of pi as a number whose sequence of digits is random is a bit of a weak point of the argument in the post. It is not even known whether every digit 0-9 appears infinitely many times in pi (a weak version of the normal number conjecture). So we do not really know (but strongly believe) that the sequence of pi digits would truly appear random. This of course does not detract from beautiful arguments and the…

I thought every pattern is encoded in Pi. If so then by contradiction you need infinitely many 1s for example. If number of ones is finite number N, let pattern be 1 repeated N+1 times. =>Edit my presumption is an open question ;) I misremembered.

Re: Connections in Math: the two kinds of random

#22

Post by AnotherGoodName »

amluto wrote: post #19
AnotherGoodName wrote: post #12

This is under-taught in comp sci so I'll say it in all caps for visibility. THERE IS NO KNOWN GENERIC WAY TO MEASURE INFORMATION ENTROPY!!!! Seriously. There isn't. You might say 'but measure the number of 1's vs 0's' and i'll just reply with '101010101010 repeated'. So you up it and start saying ok maybe measure frequencies of pairwise bits then and i just reply by cycling 00,01,10,11 endlessly etc. Frequency counts…

> This is under-taught in comp sci so I'll say it in all caps for visibility. THERE IS NO KNOWN GENERIC WAY TO MEASURE INFORMATION ENTROPY!!!! Both your comment and the OP seem to conflate a distribution with a sample from a distribution. A distribution over strings has entropy. A single string can have a Kolmogorov complex but does not have entropy in the Shannon sense per se. When you write a compression algorithm,…

>A distribution over strings has entropy.

You have to limit yourself to each string being independent for that to be true which is a limitation that leads to the impossibility of calculating entropy generically.

Re: Connections in Math: the two kinds of random

#23

Post by smalltorch »

I've been down this rabbit hole.

I tried to make a codebook of everything. You can get surprisingly good compression by assigning words and phrases to numbers.

My particular attempt had phrases up to 12 words.

No grammar or anything...to test the program, when I had a random thought, I tested to see if I could encode that thought. I could and on average the thought/message was compressed by 2. There was very few times where I wasent able to encode the idea into the available building blocks or language model of the database.

https://i.postimg.cc/WpBcB4HK/IMG-20260510-103853.jpg

Re: Connections in Math: the two kinds of random

#24

Post by zerobees »

peterashford wrote: post #16
andytratt wrote: post #8

there are many instances of claude in here, so not sure what that disclaimer was about.

how do you know?

The author admits it in the discussion of one of their other submissions: https://news.ycombinator.com/item?id=48799568

Apparently, the disclaimer was "put as a joke". Must be an eclectic sense of humor.

Re: Connections in Math: the two kinds of random

#25

Post by superposeur »

I don’t understand the claim that Kolmogorov lower bounds are uncomputable. Three digit strings are unlikely to run as a program so surely 3 is a lower bound on Kolmogorov of the first million digits of pi, no? To tighten bound, one would need to try out every 4-digit program, every 5-digit program, and so on. Either these produce the first million digits of pi or they don’t when the program is run, so each possibility is checkable in finite time, no? There must be something I’m missing here.

Re: Connections in Math: the two kinds of random

#26

Post by pwdisswordfishq »

superposeur wrote: post #25

I don’t understand the claim that Kolmogorov lower bounds are uncomputable. Three digit strings are unlikely to run as a program so surely 3 is a lower bound on Kolmogorov of the first million digits of pi, no? To tighten bound, one would need to try out every 4-digit program, every 5-digit program, and so on. Either these produce the first million digits of pi or they don’t when the program is run, so each possibili…

How long is the program which enumerates all N-digit programs?

Re: Connections in Math: the two kinds of random

#27

Post by prox »

skybrian wrote: post #11
andytratt wrote: post #8

there are many instances of claude in here, so not sure what that disclaimer was about.

Maybe the author has been overly influenced by Claude's writing style?

I think this is what we are going to see more and more, so people get exposed to the writing style and start to (un)consciously copy it.

Re: Connections in Math: the two kinds of random

#28

Post by doctor_phil »

Overall an interesting blog post, but the author makes this claim several times:

> So you can never close the case on even one candidate, let alone all of them at once, which means the lower bound stays sealed.

Which is simply not true. The specifics depends on what language you use, but let's take Turing machines as an example. Many candidates are easily disproven: ones that halt immediately, ones that have no rule for writing a "1", ones that have no rule for halting and so on. It's impossible to write a program that can handle every possible candidate though.

And if your string is short enough, let's say the string you are investigating is "0011" then you CAN sit down and check all Turing machines of size 4 and lower. This is essentially what the https://bbchallenge.org/ project did.

For Turing machines we have determined if they halt or not for all machines up to 5 states. It is very computationally hard to push this limit further, but we don't know where the theoretical limit is. We have some large upper bound where a Turing machine computes something that we know is independent of ZFC (see Scott Aaronson for more details), but many suspect that the limit is way lower.

Re: Connections in Math: the two kinds of random

#29

Post by doctor_phil »

superposeur wrote: post #25

I don’t understand the claim that Kolmogorov lower bounds are uncomputable. Three digit strings are unlikely to run as a program so surely 3 is a lower bound on Kolmogorov of the first million digits of pi, no? To tighten bound, one would need to try out every 4-digit program, every 5-digit program, and so on. Either these produce the first million digits of pi or they don’t when the program is run, so each possibili…

I agree, producing a lower bound is possible. It's practically very hard to give a good lower bound though. Many programs do not terminate, so we don't know if they do produce the right output eventually. In practice the best that has been done on Turing machines is that we have now proved which 5-state machines halt and which don't. So proving any lower bounds larger than that is practically impossible.

Re: Connections in Math: the two kinds of random

#30

Post by Ono-Sendai »

Kolomogorov complexity as an objective measure of the information contained in a string just doesn't work. It depends entirely on the language used for the program, and for any string, in some language, the complexity is zero.

See https://forwardscattering.org/page/Kolmogorov%20complexity

And no, the invariance theorem doesn't save you.

Post reply on HN