On Wed, Jan 28, 2015 at 10:22:40PM -0800, 'Chris de Morsella' via Everything List wrote: > > > 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.
No - there is a difference between a nameable number and a computable number. All the examples you give above are computable numbers (which are also nameable). But \Omega, or Turing's halting probability is an example of a nameable number that is mathematically well defined, but nevertheless, not computable. We have been able to calculate Omega to a few bits, but knowing \Omega to say 10,000 bits will tell us the answer to questions like Goldbach's conjecture, the Riemann hypthesis and most other well-known mathematical conjectures. See page 218 of Li and Vitanyi, (Intro to Kolmogorov Complexity). > > > > I realize now, I should have used the term irrational number. > > > > 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. > > > > Omega is a construction measures the probability that a randomly constructed > program will halt and that “measurement” can take on an infinite number of > values. So though it is treated as a non-computable value; it is more of a > conceptual construction. > Oops! But \Omaga has a well defined real value between zero and one. It doesn't take on an infinite number of values. What is true is that there is only a countable number of nameable number too - most real numbers are not even nameable, let alone computable, > > > I find it amusing how most people mistakenly think that making a random > number is easy, when in fact doing so – purely with software – is more than > just hard; it has so far proven out of reach. Perhaps quantum computers may > be able to. Otherwise we need a hardware detector of physical quantum > phenomena to generate a random value. > Check out HAVEGE, and Linux's /dev/random, which is based on the same idea. OK, its not strictly from software, but relies on the hardware the software must run on. > > > > > > > > > > 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. > > > > Precisely, and another way of making the point I was trying to make that > point of view is often the critical driver of a contextual complexity; e.g. > the complexity of square root of 2 is low from the bird’s eye point of view > of the entire (infinite) output, but becomes high for points of view > constrained to local zones somewhere along the infinite output stream. > > > > >>This is not obvious. We may find an algorithm computing quickly decimals at > >>anyy place of a computable numbers. That has been proven for the > >>(transcendent) number PI, and it would be astonishing it could not been > >>proven for sqrt(2), but I have not heard if that has been proved. > > > > It seems to me that those proofs depend on knowledge of the > algorithm/program. That I can see being the case. If you possess the > knowledge that it is PI you are computing the given range in the output > stream for, you have a privileged point of view. > > However, what if you have absolutely no knowledge of the algorithm/program > that is responsible for generating the resultant output. It could be any > infinite number of programs (or random collections of programs, you the > observer does not know). All you have is a seemingly purely random series of > number strings. If the individual number strings were kept rather short (say > under 1000 digits), then it would be unlikely that any kind of subtle > patterns could become discernable for such a small sample size. The number of > such small strings could be vastly numerous, with each representing a truly > random order scrambled packet. > > The key point I am trying to make is that without a priori privileged > knowledge of the f() being run (along an infinite recursion; resulting in > infinite output) if the resulting output stream is highly disordered -- and > hence has a very low quotient of compressibility -- then it would be > extremely hard if not impossible to work back from -- even a massive -- > repository of such data packets to the actual f() or array of f() that > generated the scrambled packets. > > -Chris > > > > Bruno > > > > > > > > > > > > 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. . > > > > Different chunks of the output stream may be compressible to varying degrees > (even if perhaps minutely varying degrees), but based on the highly chaotic > nature of this particular stream – to as far out as it has been calculated by > us – my guess is that there could be no significant compression. > > Turing was a math genius; information science owes him a great deal. > > > > >> 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. > > > > > > Exactly – you never know what algorithm, or even some other stretch of the > infinite output stream resulting from the infinite evaluation of 2^(1/2). > Any such coincidental knowledge could not lead back to a proof, because it > could be produced by an infinite number of algorithms. The most that could be > said is that the square root of 2 generates this given ordered set of digits > at some given range of its output. But correlation does not by itself prove > causation. > > Now supposing these unfortunate researchers began trying to build a map of > these data chunks mapping correlating regions of the vast array of all of > their known physical constants and math algorithms trying to see by brute > force correlation if a winner would emerge. I feel that instead no winner > would emerge. Many candidates would be eliminated, if their output was > predictable and any one of the growing collection of perceived packets could > be proved to be an impossible series of values for that candidate; however > the ones that would be left would be very large (theoretically potentially > infinite). > > No matter how many regions of correlation were found nothing more could be > said than that. > > > > > > >> 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.. > > > > Yes, I can see that. > > -Chris > > > > 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. > > > > -- > 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. > > > > http://iridia.ulb.ac.be/~marchal/ > > > > > > > > -- > 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. > > -- > 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. -- ---------------------------------------------------------------------------- Prof Russell Standish Phone 0425 253119 (mobile) Principal, High Performance Coders Visiting Professor of Mathematics [email protected] University of New South Wales http://www.hpcoders.com.au Latest project: The Amoeba's Secret (http://www.hpcoders.com.au/AmoebasSecret.html) ---------------------------------------------------------------------------- -- 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.
