Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Can you generate an infinite string of bits that does not contain a given finite string?

Edit: no periods in the infinite string, of course



http://en.wikipedia.org/wiki/Normal_number#Properties_and_ex...

Sure... the infinite string of 1s, or the infinite string of 0s, or the infinite string of 0s and 1s that is made up of only decimal 3s and 7s. There are an uncountably many number of non-normal real numbers like this, even though the infinite amount of normal real numbers is bigger.


> There are an uncountably many number of non-normal real numbers like this, even though the infinite amount of normal real numbers is bigger.

How sure are you with that one? Mind to supply a proof?


I have no proofs; I don't think very many proofs exist with regards to this topic.

From what I've been able to gather, I think the cardinality of the normal and non-normal numbers are the same, even though the non-normal numbers are measurably greater because of probability distributions. This is a paradox that I don't really understand. http://forums.xkcd.com/viewtopic.php?f=3&t=4270


Anything related to the concept of infinity tends to be hardly understandable in an "emotional" or "intuitive" way. We can just apply the rules of logic and accept.


Alright, that makes sense, and how about pi?


Since pi is not random, we cannot say that every finite string is in it. (If it was, the probability P[s in binary representation] would be 1 for every finite s)

Actually, there is no proof and no counter proof that every finite string comes up in pi. (...that I know of)


Yes, I can:

01001000100001...

Guess what? There are uncountable ones.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: