4 ms·
I have a question for serious math nerds: are there degrees of never repeating? Like if you think of repetitiousness like escape velocity, as you get less repet
by causi 3y ago
I have a question for serious math nerds: are there degrees of never repeating? Like if you think of repetitiousness like escape velocity, as you get less repetitious the number of digits between repeats increases until it hits infinity, aka escape velocity. Can repetitiousness decrease even beyond that?
- _a_a_a_ 3y agoCantor liked this post.
- readyplayernull 3y agoTrue randomness with infinite sequences should generate infinitely repeating sequences and infinitely non-repeating sequences.
- l33t233372 3y agoI’m not sure I agree. Can you be more precise about what you mean by repeating? If you mean “contains an infinite arithmetic progression” then surely this is not true. Could you also be more precise about what you mean by true randomness?
- l33t233372 3y agoOne way of looking at things like this is from the perspective of so called Ramsey theory. Notions like syndenticity(the property of a set having bounded gaps), upper density(the lim-sup of the proportion of numbers in the set), thickness(the property of having arbitrarily large successive subsequences), etc. all capture different notions of this. Edit: let’s not forget the rich theory involved in examining if sets/sequences contain arithmetic (or geometric) progressions! The well known Green-Tao theorem about primes containing arbitrarily long arithmetic progressions is one such result. In fact, the real Green-Tao theorem says that any set which has nonzero upper density with respect to the set of primes contains arbitrarily long arithmetic progressions.
- gylterud 3y agoThere 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.
- karpierz 3y ago> 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 agoI'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 agoAny representation of any irrational number will be an endless and never repeating sequence of seemingly random digits.
- kmod 3y agoI 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.
- deleted 3y ago[deleted]