197
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
this post was submitted on 26 Dec 2024
197 points (98.5% liked)
Asklemmy
44173 readers
1926 users here now
A loosely moderated place to ask open-ended questions
Search asklemmy ๐
If your post meets the following criteria, it's welcome here!
- Open-ended question
- Not offensive: at this point, we do not have the bandwidth to moderate overtly political discussions. Assume best intent and be excellent to each other.
- Not regarding using or support for Lemmy: context, see the list of support communities and tools for finding communities below
- Not ad nauseam inducing: please make sure it is a question that would be new to most members
- An actual topic of discussion
Looking for support?
Looking for a community?
- Lemmyverse: community search
- sub.rehab: maps old subreddits to fediverse options, marks official as such
- !lemmy411@lemmy.ca: a community for finding communities
~Icon~ ~by~ ~@Double_A@discuss.tchncs.de~
founded 5 years ago
MODERATORS
Can you prove this? Or link a proof?
I don't know of one but the proof is simple. Let me try (badly) to make one up:
If it doesn't go into a loop of some kind, then it necessarily must include all finite strings (that's a theoretical compsci term).
Basically, take a string of any finite length, and then view pi in inrements of this length. Calculate it out to double the amount of substrings of length of your target string's interval you have [or intervals]. Check if your string one of those intervals. If not, do it again until it is, doubling how long you calculate each time.
Because pi is non-repeating, each doubling in intervals must necessarily include at least one new interval from all other previous ones. And because your target string length is finite, you have a finite upper limit to how many of these doublings you have to search. I think it's n in the length of your target string.
Someone please check my work I'm bad at these things, but that's the general idea. It's also wildly inefficient This doesn't work with Infinite strings because of diagnonalization.
Your first sentence asserts the claim to be proved. Actually it asserts something much stronger which is also false, as e.g. 0.101001000100001... is a non-repeating decimal which doesn't include "2". While pi is known to be irrational and transcendental, there is no known proof that it is normal or even disjunctive, and generally such proofs are hard to come by except for pathological numbers constructed specifically to be normal/disjunctive or not.
Let me give another counterexample. Let x be the binary expansion of pi i.e. the infinite string representing pi in base 2.
Now you will not find 2 in this sequence by definition but it's still a non-repeating number.
Now one can validly say that we restricted our alphabet and we should look only for finite strings with digits that actually occure in the number. The answer is the string "23456789" concatenated with x.
That's like saying your car is busted because it can't drive on a road made of broken glass.
That's mathematics. It do be like that sometimes. Counterexamples can be stupid but still valid.
It's on you to prove your claims.
No this does not work. Counter example can be found in the comments here of a non-repeating number that definitely does not contain all finite strings.
Edit: I think the confusion is about the word non-repeating. Non repeating does not mean a subsequence cannot repeat but that you cannot write the number as a rational or with a finite decimal representation. I.e. it's not 3.ba repeating. Where a is a finite sequence that repeats infinitely and b is a finite sequence.
Edit edit: another assumption you make is that pi does not go into a loop of some kind. You would need to prove that.
Are you talking about a different base/character set? I think every single person understands that.
See my other comment