Hacker News Reader

Comment by gylterud | Hacker News Reader

There is Kolmogorov complexity, which is (relative to a programming language) a measure of how easy a sequence is to produce algorithmically – i.e. what is the length of the shortest program which can produce the sequence. Most mathematicians believe that not all sequences can be produced algorithmically, so this leaves some sequence too complicated to have a finite Kolmogorov complexity. But you can go on to the infinite by adding oracles, and start assigning infinite ordinals to sequences, depending on how many oracles you need for a given sequence. If a program uses an oracle for the halting problem, say, you nominally add ω to its length.

All the repeating sequences have finite Kolmogorov complexity. So, if you want, you can say that the sequences with infinite Kolmogorov complexity have even lower repetitiousness than the ones we can produce algorithmically. And this will go on and on through the countable ordinals.

View on HN

> Most mathematicians believe that not all sequences can be produced algorithmically, so this leaves some sequence too complicated to have a finite Kolmogorov complexity.

Isn't this just true?

The set of algorithms is countable, and the set of sequences of real numbers is uncountable.

I'm not clear on the definition of sequence such that you could have one without having a description of how to produce it? Can you have a sequence of random numbers?

Any representation of any irrational number will be an endless and never repeating sequence of seemingly random digits.

I think the term of interest here is non-computable: irrational numbers can have finite kolmogorov complexity.

You're kind of "begging the question" here, where you're assuming that non-computable numbers exist and then using that to show that some numbers are non-computable. You can definitely show that these things exist, but that relies on "believing" the set of axioms that you used to prove it.

How do we identify a specific non-computable number?

They are necessarily non-constructive existence proofs, for sure. You're not alone in some potential unease with that: https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_...

It depends on believing in classical logic. Constructive mathematicians can instead choose to adopt intuitionistic logic and postulate Church thesis, which states that all functions, and thus sequences, are computable.

IANAMathematician, but it's "true" in the sense that we primarily use a set of axioms (ZF/ZFC) which produce this result. But in a sense one of the axioms is that these things exist (powerset axiom), so this result is a bit less illuminating than one might hope.

My understanding is that we can reason about these sorts of non-constructible sequences but we can't really know if they "really exist" because it's not clear what that even means if their existence has no implications for physical reality (which is possible but not known). So now we're into the territory of whether there is such a thing as abstract truth independent of reality.

I wrote a blog post in the past about my reading on this topic, and I can't claim that's it's accurate but at least I tried to talk about this subject: https://blog.kevmod.com/2022/04/09/do-the-real-numbers-exist...

The set of algorithms is countable

That is assuming finite algorithms. I’m curious if infinite algorithms exist and/or considered in maths.

The internet says that an algorithm is finite by definition, but it’s hard to search for “infinite algorithm” because everyone talks about termination instead.

Aren’t self-modifying programs a potential implementation of an infinite algorithm?

Reply on news.ycombinator.com