On Sun, Jan 25, 2015 'Chris de Morsella' via Everything List < [email protected]> wrote:
> I agree it is devilishly hard to produce a truly random stream and a lot > of brain power has gone into trying to do so, because of the strategic > importance of doing so. It's not merely hard it can't be done, you will never be able to produce true randomness in a computer with just software, you'll need to add a hardware gadget for that. > > > Ten divided by three results in a non-computable number > Ten divided by three is a computable number, Turing meant something else by a non-computable number. There are algorithms that will allow you to compute a decimal that is arbitrarily close to 10/3 or the square root of 2 or PI or e, or any other real number that has a name; tell me how close you want to get (provided the distance isn't zero) and I'll give you a finite decimal for it. But Turing proved that most numbers on the Real number line, nearly all in fact, are not like that at all; there are no algorithms that can even give approximations for them. It's sort of ironic that although these non-computable numbers are vastly, in fact infinitely, more common than the computable numbers that everybody is familiar with nobody can point to and name a single one of them... well Chaitin managed to name one and called it Omega, but he couldn't point to it. > > take any local section of the stream – of square root of two is instead > very difficult to compress > That's true, the entire square root of 2 decimal expansion would be easy to compress, but a local section of it, say just the digits from digit 1000 to digit 2000, would be far more difficult to compress. Is there a algorithm that will produce just those digits that is shorter than a list of those 1000 digits? Maybe there is, or maybe not, Turing also proved that in general there is no way to know if there is a algorithm that will produce a sequence of numbers that is shorter than the sequence itself; and even if there is and you happened to find a algorithm that worked Turing also proved that in general there is no way to know if it is the shortest algorithm. . > >> By "seemingly random" I assume you mean it came from a algorithm. >> > > > Yes, it is not truly random, but the chunks have been randomly scrambled > in the transmission > OK. >> How is the data stream scrambled, by another algorithm or a physical >> random process such as radioactivity decay? > > > > Assume by some physical random process – assume for the sake of > discussion that the ordering of the packets has been truly scrambled. > OK > Also need to assume that the key first packet containing the portion of > the number to the left of the ‘dot’ is explicitly excluded from the > transmission. Only packets of numbers are transmitted; no other symbols. > OK > now I am not sure, perhaps square root of two will leave subtle patterns > in the apparently random series that a clever algorithm could pull out. > This possibility increases as the chunk size increases, > The square root of 2 has been calculated to, I don't know probably about a trillion digits, but regardless of the chunk size if the chunks were picked at random from the entire infinite sequence of digits then the probability that any chunk you received came from those first trillion digits that you would recognize would be zero. And even supposing one of the chunks you got did contained a sequence of 1000 digits that were identical to the first 1000 digits of the square root of 2 that doesn't prove it came from a algorithm that produces the square root of 2. It has been proven that any finite sequence of digits you can name exists somewhere in the decimal expansion of PI or e, your social security number will be out there a finite distance into the expansion and so will the first 1000 digits of the square root of 2. So maybe the number they're sending you didn't come from a algorithm for the square root of 2 at all, maybe it came from a PI algorithm, or a e algorithm. > >> In other words will the recipient ever be able to predict what the next >> digit will be? > > > > I was thinking more of the strong challenge of reassembling the packets > into their correct order; by working back to a proof of the function that > generated the output stream, > That would be pretty much the same thing, if you can reliably predict the next digit you must have figured out what the algorithm was that produced the digits.. John k Clark -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
