5 ms·

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

> 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.

fsckboy 3y ago
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?
- rbanffy 3y ago
  Any representation of any irrational number will be an endless and never repeating sequence of seemingly random digits.
  - kmod 3y ago
    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.
    - rbanffy 3y ago
      How do we identify a specific non-computable number?
- kmod 3y ago
  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_mathematics) https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_...
gylterud 3y ago
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.
deleted 3y ago
[deleted]
kmod 3y ago
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/ https://blog.kevmod.com/2022/04/09/do-the-real-numbers-exist...
wruza 3y ago
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.
- chongli 3y ago
  Aren’t self-modifying programs a potential implementation of an infinite algorithm?

fsckboy 3y ago

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?

rbanffy 3y ago
Any representation of any irrational number will be an endless and never repeating sequence of seemingly random digits.
- kmod 3y ago
  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.
  - rbanffy 3y ago
    How do we identify a specific non-computable number?
kmod 3y ago
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_mathematics) https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_...

gylterud 3y ago

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.

deleted 3y ago

[deleted]

kmod 3y ago

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/ https://blog.kevmod.com/2022/04/09/do-the-real-numbers-exist...

wruza 3y ago

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.

chongli 3y ago
Aren’t self-modifying programs a potential implementation of an infinite algorithm?