Got to be careful here. Clearly there are programs of finite size that spit out the digits of Pi. But the program plus its working data is not finite state. (And the ZL stuff mostly applies to string-in-string out stuff. Vs. Just string out.)
The simplest type of Kolmogorov complexity and such addresses program size only. How much memory the program uses isn’t relevant.
So you have to careful here. Are you talking finite program or finite state, etc.
(Kudos for putting Ziv before Lempel there. How it got perverted into LZ almost everywhere is beyong me. Even worse is “LZW” where the Big Idea was Welch’s. It really should be “WZL”.)
We don’t have to restrict ourselves to “merely” computable numbers. E.g., Chaitin’s constant is an example of an number that has a finite description which isn’t computable but is normal. It is basically (one of) the “densest” numbers in terms of representing useful information per digit. Even if Pi were normal, it couldn’t be anywhere as good as Ω. Given the first 100 digits of Ω and you could rule the world.
Searching pi for English snippets? If God really had used the digits of pi to encode the History of the World in English, mightn’t he have used a Huffman code? We could find desirable strings earlier then.
However, even fixing the bit lengths there are still hundreds of quadrillions of ways to assign a Huffman code. I don’t know how we’re supposed to search for a simple limerick, let alone the Meaning of Life.
One thing though — long before you find the Bill of Rights encoded in the digits of pi, I’m afraid you’ll find zillions of versions with the N’th Amendment drastically modified. :smack:
But it would be a lot easier to find arbitrary strings if you don’t require that the strings be ASCII codes. Like, you could invent your own code, and search for your string using DorkCode instead of ASCII. And if you find a string that’s pretty close, no problem, just change your definition of DorkCode to make the digits match the string. Easy!
And this is how people find secret messages in the Bible. Can’t find a message using the first word of every chapter? Well, how about the 17th letter on alternating pages? No? How about the 16th on even pages and the 27th on odd pages? Oh, that spells out “O-B-A-M-A-S-U-X” God is speaking to us!
Nitpick: This code lacks the prefix property. In particular note that when our OP, Left Hand of Dorkness, finds his name in the digits you can laugh and claim that he’s found Lellt Hand oll Dorkness instead!
Chronos already noted that normality is more than just containing every finite string; it’s containing every finite string of each given length with equal asymptotic frequency. For terminological convenience, I’ll furthermore note that simply containing every finite string is sometimes called being “disjunctive”.
Also, I want to say this: often in these discussions it comes up that “almost all” digit-sequences are normal, and therefore we should expect π’s to be normal. Well, it’s true that there is a familiar probability distribution on digit-sequences such that almost all are normal. But it’s just as well true that there is a probability distribution on digit-sequences such that almost all are non-normal. Or 37%, or any other thing. There are a great many probability distributions on digit-sequences. The relevance of any of the aforementioned ones to the plausibility of π’s normality is tenuous.
Given a finite string S and an infinite sequence W, some of the digits in W are the start of S’s, and some of the digits in W are not the start of S’s. At any particular point finitely far into W, some proportion of its finitely many digits so far have been S-starters. This proportion fluctuates as we go further into W; its limit (in the sense of calculus, presuming you are familiar with this notion) as we go arbitrarily far is the asymptotic frequency of S within W.
You are playing roulette. You expect, if the wheel is fair, that each number on the wheel–from 00 to 36–to come up equally often. For a small number of spins this won’t happen, but if you spin it a million times, a billion times, and so on, you expect them to come up equally. The “asymptotic frequency” is just how often you see each one come up as you spin more and more times.
We can also look at “strings”, which is just a way of looking at more than one number in a row. (00, 00) should come up just as often as (23, 34) (in that order!). Likewise for sequences as long as you want (“every finite string”). This is what is meant by “every finite string of each given length [has] equal asymptotic frequency”. All the single numbers come up equally, as well as all the sequences that are a million numbers long.
What this means is that even if we knew that pi contained every finite-length string, unless you can prove it’s “normal”, you don’t know that it doesn’t have huge sections of “123123123123” (or whatever) interspersed by more interesting stuff.
Yeah; although, even π being normal (without any further quantification on the convergence timing of that normality) would technically have no conflict with it having huge strings doing arbitrary weird bizarre stuff at the beginning. Literally nothing we could possibly observe in any finite number of digits of π has any conflict with π being normal or not; the property is independent of anything in any initial finite segment.
:smack: