Re:Mathematics: Came across the following gag. Is it true?
by notatoad on Friday October 19, 2012 @04:37AM
(#4672726)
It's not proven, it's the definition. If there is a subsequence that isn't contained in a non-repeating infintely long sequence, then it isn't a non-repeating infinitely long sequence.
[ Parent
| on HN ]
Re:Mathematics: Came across the following gag. Is it true?
by xyzzyz on Friday October 19, 2012 @04:52AM
(#4672760)
This is not true. For instance, sequence 00 does not occur in sequence
010110111011110111110111111...
which can hardly be described as "repeating" (or periodic) sequence.
The point here is normality. Fix alphabet A having b letters. We say that a sequence S of elements of A is normal if, for every word w, we have
lim n->inf C(S, w, n)/n = b^(-k)
where C(S, w, n) is the number of occurrences of w in first n letters of S, and k is length of w. More intuitively, S is normal if every word occurs in S with the same asymptotic frequency.
So, if a sequence does not contain some word as a substring, it cannot be normal by above definition.
Re:Mathematics: Came across the following gag. Is it true?
by ColinWright on Friday October 19, 2012 @04:42AM
(#4672736)
You're conflating two things. The technical definition of "normal" is that it contains every finite string as a substring. That will imply that it's infinite and non-repeating.
However, you can have a string that is infinit and non-repeating but not normal.
Pi is infinite and non-repeating, but it is not known to be normal.