Once again, Sal and Friends Butcher Information Theory

Davetard only imagines he outed Orac, Orac's identity has been an open secret for years.

Dude,
If you want to understand the world of Uncommon Descent, you're going to have to study up on Disinformation Theory.

Oh, I just love that zinger at the end.

The article goes off the tracks in its 9th sentence, which exposes the misconception at the agenda level:

"Information is not gratis because it needs an intelligent source."

This is flat wrong, in the sense that Shannon used "information", based on previous authors at Bell Labs.

See my description, with citations, on my paper responding to Sal on an earlier Good Math Bad Math thread, at the NECSI wiki, of the basic terminology of the Shannon mode.

The dealing from the bottom of the deck happens again with the rhetorical ad hominem question: "Why - in a sense - are the works of great mathematicians as K.Gödel, A.Turing, G.Chaitin, J.Von Neumann "friends" of the Intelligent Design movement and - in the same time - "enemy" of Darwinism, the biological theory according to which life and species arose without the need of intelligence?"

It is hard to explain the mix between right, wrong, and not even wrong in: "So information is the link between the field of mathematics and the field of biology."

An extreme case of putting words in someone's mouth is: "To say it in few words, Gödel's works in metamathematics, Turing's ideas in computability theory, Chaintin's [sic] results in algorithmic information theory (AIT) and Von Neumann's researches in informatics are friend to ID because all are different expressions of a unique universal truth: 'more' doesn't come from 'less'; a lower thing cannot cause a higher thing; causes are more than effects; intelligence stays above and its results below."

Your demolition, Mark, is correct on this barrage of bullpuckey. There is also a hint of "as above, so below" medieval hermeticism in the cryptic "a lower thing cannot cause a higher thing" -- which might have come from the spiel of any wandering fraudulent alchemist.

There isn't the low cunning I expected from an ID web page. This is so stupid, such total GIGO, that I'd think any person wandering onto it would Google a few times on the names abused, and see that the descriptions of Gödel, Turing, Chaitin, and von Neumann bear no resemblence to what any other web page says about them.

This is no better than supporting George W. Bush by saying "George Washington, Thomas Jefferson, and Anraham Lincoln said that preemptive strikes on ideological enemies are demanded by the Constution, and the Monroe Doctrine says that the United States must fight them over there to keep from fighting them over here."

Gödel, Turing, and von Neumann are not here to defend themselves, but Chaitin is, and might need to discuss with an attorney whether or not libel is going on, or whether it is best to let 3rd parties slug it out.

I found the web page a digusting display of dishonesty. I feel like getting eyedrops to wash the fertilizer from my stinging eyeballs.

Seemingly, Sal's math is as bad as his biology.

steve s:

I know that Orac's real name is an open secret. But that doesn't reduce the malice on DaveScott's part in trying to out him. His purpose was to harm Orac by revealing his real name. It was done for absolutely no valid purpose, to make no real point - just in the hope that he could do some harm.

In general, I don't like the idea of outing like that. Sometimes, there's a good reason for it (revealing sockpuppets, or when a pseudonym is being used for the purposes of harming someone); but in general, if someone chooses to not reveal their real name on the net, I think that that should be respected. I know DaveScott is a pseudonym; and I know his real name - but I'm not going to go and trumpet that to the world. He's not harming anyone by using it, and so I'm not going to step up and announce what his real name and contact information are.

I think Orac's got a very reasonable reason for using a pseudo: he doesn't want his blog to be the first thing that patients see when they look him up on the web. "Outing" him just for spite is just a shitty thing to do.

There is a different category of error in the paragraph "In a scientific theory modeled as a computer program the inputs 'I' are the observations of past events. The outputs 'O' are the predictions of future events. Outputs are derived by the inputs by means of the natural laws. Natural laws are simply the instructions of something we can call 'natural software', or 'software of the universe', i.e. the above computer program. In fact laws, rules, specifications, instructions are quite similar from this point of view. We can say that lesser the computer program is better the theory is. Also for this theory-program one can define the algorithmic complexity H(p). If H(p) is almost equal to 'i' we stand in front of a poor quality and useless theory. In practice it does not tell us anything more that the input observation data tell us yet from the beginning."

First, scientific theories do NOT have the past as an input and the future as an output. Many scientific theories use state variables, as opposed to history variables. Thus, the past is not an input. The future unfolds from the present. The past only matters to the extent that the scientist has examined it to produce a theory; the theory itself has the past cut away.

Closer to the truth of "minimum description length" applied to scientific theory, to excerpt from wikipedia

en.wikipedia.org/wiki/Minimum_description_length

"... Any set of data can be represented by a string of symbols from a finite (say, binary) alphabet. "The fundamental idea behind the MDL Principle is that any regularity in a given set of data can be used to compress the data, i.e. to describe it using fewer symbols than needed to describe the data literally." (Grünwald, 1998. See the link below.) Since we want to select the hypothesis that captures the most regularity in the data, we look for the hypothesis with which the best compression can be achieved...."

One typically compares theories by this sort of encoding:

Associate each theory with a string as follows: concatenate the axiomatic descitption of theory to the appended string which encodes the data measured and which is being used to evaluate the theory.
Then see how closely the theory predicted/postdicted that experimental data.

One problem is that theories which are good at prediction are typically not as good at postdiction, and vice versa. This can be established in Bayesian models, before we even get into measuring entropy and compressibility.

Uncommon Descent picks an interesting subject, but badly misrepresents what Solomonoff et al were doing, and what the input and output of a scientific theory should be.

It is very tricky to axiomatize Occam's Razor. Centuries of false starts. Some very promising results today, but they are real Math, with very careful definitions, theorems, and proofs. Sadly, the ID crowd does not seem to have produced a single person who can read an article in, say, IEEE Transactions on Information Theory, and be able to do anything more coherent than cite the paper by author and title and date. Actually reading the papers is easier than writing them, but takes clarity and education. I've written a 100-page manuscript on MDL and Occam's razor, from which two published papers have been extracted, and presented at international conferences.

The subject is, as I say, very interesting. It has not penetrated to the awareness of most logicians, let alone the Biology community. But when it does, it will bear essentially zero correlation with the farrago by ID handwavers.

Yet another mashup of valid and invalid occurs in the paragraph [I've numbered the sentences]:

"For example think of the theoretical strives the modern physicists apply to discover a so-called Theory Of Everything (TOE) [1]. A TOE should be a theory able to explain all the natural phenomena beginning from a finite number of physical-chemical laws mathematically described [2]. A scientific theory in general is a mathematical theory, an axiomatic formal system [3]. For these reasons the results about the Gödel's incompleteness and the Turing's limits of computability affect all the scientific theories too [4]. As a consequence we get a fundamental 'irreducible complexity' of the 'kernel' of the same physical world. [5]"

[1] and [2] are acceptable summaries to me, and relevant to, for example, the String Theory Wars [see the blog "Not Even Wrong"].

[3] is hideously wrong. Scientists use Math, but are not mathematicians. "Axiomatic truth" [as with Euclid] is foundationally different from "Empirical truth" [the Scientific Method]. These in turn are both different from "Legal-Political Truth", from "Aesthetic truth", and from "Revealed religious truth." The whole Creationist agenda is to conflate "Empirical truth" with "Revealed religious truth." The ID scam tries to hide the connection with religion, in this case by incoherently stirring in "Axiomatic truth" as with K.Gödel, A.Turing, G.Chaitin, J.Von Neumann to hide the flavor of burning bushes and The True Cross.

I tend to agree with [4], and this is a fascinating area. See John Baez's blog on a blogger/science writer who gave quite a brilliant lecture on that connection, to Physicists and Mathematicians a few months ago.

What on Earth is meant by 'kernel' in [5]? It seems to somehow abuse a mathematical usage of a term (as in Kernel of a convolution integral) or maybe in computer programming (as with Linux Kernel) with -- I don't know -- Amos 9:9 "For behold, I am commanding, And I will shake the house of Israel among all nations as grain is sifted in a sieve, yet not the least kernel will fall on the earth."

Here you go again, misunderstanding Gödel's theorems. The explanation you quote is, in fact, exactly correct, except for the confusion of "finite set of axioms" with "finite presentation of first-order axioms". Moreover, this:

You can describe all of arithmetic using a formal system with a finite set of axioms; in fact, Gödel himself proved that, in his completeness theorem.

is utterly false. Gödel's completeness theorem applies only to first-order predicate logic. Arithmetic is not first-order predicate logic. The Wikipedia articles to which you link make this clear; the one on the completeness theorem doesn't even talk about arithmetic or numbers of any kind.

I'll give you a demonstration. Let's say T is a recursively enumerable theory true on the natural numbers (therefore omega-consistent), and it contains all the basic facts about arithmetic. By Gödel II, the formalization of the statement Con(T) is neither provable nor disprovable in T. It is, nonetheless, true; T must be consistent, because it has a model. Thus, if I take the theory T' = T + Con(T), I'll have a new theory which strictly supercedes the old one. I could do this over and over again, of course.

Thus Gödel's theorems, if one presumes the existence of a mathematical universe, do in fact show that mathematics supercedes any attempt to axiomatize it.

Whether this means that mathematics itself is incomplete is a somewhat different question, and I certainly don't want to argue that this somehow supports Sal's twaddle (what do the limits of formal mathematics have to do with the limits of biological systems?).

What I'm curious about regarding this whole ID-phenomenom, is, what are their actual goals? Surely by now these people must realize that their efforts will not magically transubstantiate into anything resembling solid science. Sure, some of these people might have a great deal of personal fame & fortune riding on this BS, but do they think that they will be able to keep at it indefinitely?

And what if ID won out in the public? Would these people really prefer a society, where science (and presumably other endeavours) are subjected to some form of theological evaluation, before being accepted or allowed? That some fields of scientific inquiry would be banned, because the methods or conclusions do not fit their preconceived religious notions of how the universe should be?

Thanks for the deconstruction of another lame UD article. It appears ID has to recruit from the dead to bolster it's case. There's probably some zombie joke in here, but I've had a long day.

Regarding the "outing" of Orac, I'd say it went farther than using his name - he essentially calls him a shill for Big Pharma and tosses in conspiracy theories to boot. Normally Dave's just a posturing brittle poseur, but this is pretty much on the high level of viciousness - my guess is Dave isn't just fond of Evolutionary science, but a great deal of other science as well. There's definitely a conspiracy theory mentality at work here.

To Chad Groft: Quick question. I've yet to quite understand what the word 'true' means in the incompleteness theorem.
Are all the models of T also models of Con(T)? If not, is it correct to say that Con(T) is true? Wouldn't it be more proper to just call it satisfiable? If they are, shouldn't Con(T) be rightfully taken as a logical implication of T, and we could prove Con(T) from T in the newly formed logic?

[Flaky] Of course they'd prefer such a society. Their pathologically self-serving agenda is anti-enlightenment, its only possible "success" the establishment of some kind of medieval theocracy in which they can play the high priesthood, living pretty on the income from plenary indulgences and selling a line of hypocritical bullshit to credulous proles for whom they have nothing but contempt. The spectacle is beyond nauseating.

I wonder what contorted sophistry they'd employ to include "The Chemical Basis of Morphogenesis" in this attempt to portray Turing as a "friend" to ID?

I've seen that misuse of Gödel before, and I think Berlinski was the perpetrator. His essay was contained in a volume of arguments against evolution, which I paged through in a bookstore and sensibly declined to purchase.

I've seen that misuse of Gödel before, and I think Berlinski was the perpetrator. His essay was contained in a volume of arguments against evolution, which I paged through in a bookstore and sensibly declined to purchase.

Well ... that was a weird error message. Sorry for the resulting double post!

Sal should just cut to the chase and claim that ID is "true, but not provable". It is the obvious fallback from provably true. The difficulties of the double secret DI research program in proving ID Theory leave only one possible conclusion, right? Faith-based research at its best...

To Flaky: No, not all the models of T are also models of Con(T). If that were the case, then Con(T) would be provable from T (that's what Godel's Completeness Theorem says).

For the classical theories (say Peano's Axioms), there is only one intended model, and "true" means true in that model. That is, it's generally assumed that there is a universe of natural numbers, namely everything one can reach in principle by starting at 0 and counting, and that there are canonical functions and relations on it (+, *, <). Sometimes these are referred to as the "standard" natural numbers. It's also assumed that Peano's axioms (call the set of such axioms T) are true when interpreted on this model.

Since the axioms of T are true on the standard model, they must be consistent. Further, if there were some natural number n which encodes a proof of a contradiction, then this number, and the proof that it does so, could be unwound to produce an actual proof of a contradiction. So the formalization of the statement Con(T) is a first-order sentence in the language of number theory, and moreover a true one.

However -- and this is the key point -- that fact cannot be proven just by reasoning "inside" the universe of natural numbers. One could take any particular natural number n and prove the statement "n does not encode a proof of a contradiction from T" by basic, finitist reasoning; in other words, it's a "simple" exercise in arithmetic. One cannot, however, prove the statement "No element of the universe encodes a proof of a contradiction from T" by such reasoning; the step outside, to say "T is true on this model" is necessary.

Going back to the first comment, there must be models A of the theory T + "Some element n encodes a proof of a contradiction from T". However, this n in the universe of A would not correspond to any "actual" natural number. That is, it would not correspond to 0, or 1 = S0, or 2 = SS0, or 3 = SSS0, etc., although all of these would have analogues in A. Such an n is usually called a "nonstandard number", and A is called a "nonstandard model". (Incidentally, there would also be nonstandard models of T + Con(T).)

To sum up, if T is satisfied by the universe of natural numbers, then so is T + Con(T), but T + not(Con(T)) is satisfied by some other model. This can be given a positive spin, though, as it implies that there is always something new to learn about the natural numbers. Namely, if our current knowledge includes some theorem T, then we can extend to the theory T' = T + Con(T), and from there to T'' = T' + Con(T'), and so forth, and each theory will include something new.

The relevant Wikipedia articles that MarkCC cites are very good sources, if you want to know more.

I'll touch on only one point in Cordova's new appearance, where he pretends to pass a judgment on Goedel's, Turing's, von Neuman's and Chaitin's views on ID, namely on Cordova's impudent and mendacious claim that Gregory Chaitin's algorithmic theory in some way supports ID.
In 1999 I posted an essay (later reproduced in my book of 2003) where I pointed to Kolmogorov-Chaitin's algorithmic theory as being profoundly incompatible with Behe's irreducible complexity concept. The algorithmic theory maintains, among other things, that an irreducible string is necessarily random. If randomness is an equivalent of irreducibility, Behe's concept of IC collapses. Neither Behe nor any other ID advocate has ever tried to rebut my thesis. Since ID advocates view IC as one of the main pillars of their "theory," the collapse of Behe's IC idea seriously undermines the entire ID set of concepts.

The algorithmic theory maintains, among other things, that an irreducible string is necessarily random. If randomness is an equivalent of irreducibility, Behe's concept of IC collapses.

The problem is that Sal attempts to conflate two different and almost completely unrelated concepts. A random (incomrpessible) binary string is only a description from which you reconstruct the object, while Behe posits mechanical irreducibility of the object itself. DNA contains non-functional elements, as well functional and non-functional repitition. That's opposed to the very concept of AIT.

Mark CC said: "I think Orac's got a very reasonable reason for using a pseudo: he doesn't want his blog to be the first thing that patients see when they look him up on the web."

I believe it also has something to do with Orac's experience posting arguments against holocaust denial under his own name in newsgroups where he was greatly outnumbered by holocaust deniers, which IIRC resulted in very real threats of harm to him.

The pun at the end left me groaning. Wonderful.

randomness is by definition uncompressible

This strikes me as one of the points where an IDiot's cognitive resonance forces him to blindly overlook the facts. (Similar to that IC simply isn't IC because of simple things like gene scaffolding.)

Dembski et al will never accept this simple fact however many times they see it, taste it and feel it. Because that would immediately reveal their stupid reversal of reality, and kill their speculations on SC and information.

> We would not expect the outcome of a purely random process to have a low (i.e., highly compressible) information content.

I don't really understand Chaitin, but I do understand a bit of Shannon. I'm struggling to understand this sentence.

First, being pedantic, I don't see the need for saying "purely random". What's an example of a "not purely random", or "semi-random" phenomenon?

That's not the important part, though. Strictly from Shannon's IT theory, all information sources are random and the compression process is that of finding a good representation for it. A random source can indeed have a very low information content.

For instance, consider a source X with alphabet {x0, x1}, and with P(x0)=0.05 and P(x1)=0.95. The entropy of this source is 0.29 bits per symbol, and a naive mapping of x0 to the binary digit 0, and x1 to the digit 1, is highly inefficient and, thus, compressible.

From the natural world, any phenomenon that can be modeled as deterministic has essentially zero information content: we know with high precision the time of eclipses, for instance. Or, an experiment could produce the same result most of the time: a drug, for example, could cure 99% of patients. It's not hard to find natural examples of experiments that are random but which, when modeled as an information source, have very low entropy.

I apologize if I'm missing something from Chaitin's theory, and my interpretation from Shannon's theory is wrong. I also appreciate any insight into why randomness and incompressibility are being equalled.

"cognitive resonance" - cognitive dissonance.

(Heh! I can see Cordova and Dembski convulse together when reading such problematic facts. In about D minor cadence, of course.)

Oh, there is so much to fisk here.

For example, they suggest that John von Neumann work on cellular automata was an inspiration for biological theories:

In turn Von Neumann developed the fundaments of informatics and studied mathematically the architectures capable of processing information. His computational model is yet the main computational model used by our computers nowadays. What's more, he anticipated times thinking theoretically how self-reproducing automata can work before living self-reproducing biological automata (i.e. cells) were investigated by molecular biologists.

That seems to be the reverse of the truth. It was biological systems that inspired von Neumann. At least according to Stephen Wolfram in his book "A New Kind of Science":

The best-known way in which cellular automata were introduced (and which eventually led to their name) was through work by John von Neumann in trying to develop an abstract model of self-reproduction in biology - a topic which had emerged from investigations in cybernetics.

To make their claim, they have to do a total fabrication of history:

The remarkable thing is that Von Neumann was able to successful conceive theoretically the mathematical model of a self-reproducing automaton without knowing as cells effectively reproduce in nature. Besides he said to biologists that necessarily a cell had to implement a system isomorphic to such automaton, before biologists themselves discovered such mechanisms. His farseeing forecast was perfectly demonstrated five years later with the discovery of the DNA and the extremely complex molecular processes of DNA transcription and traduction.

The existence of genes were famously suggested by Mendel in the 1860s. Morgan showed 1910 that the genes were situated in the chromosomes discovered 1842 by Nägeli. So the genome function and its cell implementation were known decades before von Neumann started to work on models inspired by biology 1947!!!

It was also shown 1941 that protein coding was done according to a one gene - one protein correspondence. And DNA, which was discovered 1829 (as "nuclein"), was known to hold the gene's information 1944, well before von Neumann started his work.

What happened about 5 years after von Neumann started on automata was that DNA's structure was discovered 1953. But the central dogma that describes the production of protein, transcription and translation (not the creationist "traduction") was not elaborated until 1957, 10 years afterwards.

After this blatant history revision, the creationist text finishes with suggesting that von Neumann's work is ID theory and has relevance for biology. Nothing could be further from the truth.

We know that von Neumann's design is intelligently made, but we also know that it was inspired by biology instead of inspiring biology theory. And even if it would be inspiring biological science, it would not say anything about evolution.

Natural selection may be an intelligent designer of sorts, choosing the survivors by contingent fitness and chance. But we have reason to believe it was von Neumann who put the most intelligence into his designs!

MiguelB:

This is one of the places where Chaitin and Shannon theories are very different - Shannon is coming at it from the perspective of physics; Chaitin from computer science.

In Chaitin theory, a given piece of information is very specific. Compression isn't about representing a source of information, but about extracting all redundancy from an information source. Shannon is, fundamentally, looking at analog information; Chaitin is even more abstract that digital.

In Chaitin, you have a string of symbols that you're studying. That string is known precisely. It's not an approximation. A string contains some quantity of information. The definition of the quantity of information is the minimum size of a pair of program+data which will generate that string.

In terms of Shannon theory, randomness is similar to Shannon's idea of "surprise": how easily can you predict the next character given what you know about the previous characters. In a perfectly random string, knowledge about the previous characters gives you no advantage in predicting the next character. If the previous characters allow you to predict the next, that means that the string contains redundant information - it's compressible.

There are two reasons for explicitly saying "purely random". First, there's the definition of random in Chaitin that I mentioned above: in a random string, seeing a prefix of a string gives you no information about the restof the string - in Chaitin, non-determinism is not really random. It's got a random element, but it can also contain a lot of pattern. The probabilistic information generator you mentioned would not be a truly random source in Chaitin - the knowledge of its probability distribution is knowledge of a pattern that allows you to predict the next bit most of the time. (i.e., if you guess "1", you'll be right 90% of the time.)

The second reason for being explicit about true randomness is because in computability, we see tons of pseudo-random things. For a trivial example,if I use a basic random number generator on my computer to assemble strings, those strings will look random to me; they'll pass a χ2 test for randomness; but they're not random: they can be perfectly reproduced given the initial seed value used by the RNG. So strings generated by the RNG are very low information content - because I can reproduce them with a simple RNG program and a single integer seed.

Thank you Mark. I see both theories are quite different; I need to read up on Chaitin and see if I can introduce some of his theory in my classes.

> In a perfectly random string, knowledge about the previous characters gives you no advantage in predicting the next character.

Here we have a terminology mismatch: I don't like using "perfectly random" to describe that string; I would say something along the lines of "the characters of the string are independent". The way I see it, that an event depends on another doesn't subtract from the randomness of a source, experiment, or string.

I can see the need to specify something is "truely" random, as you say. "Perfectly" and "purely" random, I don't really agree with.

I think it should be noted that the definition of "complexity" is really up for grabs, and that Kolmogorov-Chaitin complexity, i.e., algorithmic incompressibility, is just one candidate. By contrast, it seems somewhat perverse to deny the description "complex" to certain structures, for example, the Mandelbrot set, that are specified by extremely concise descriptions. Of course, since Dembski, Behe and Co. play so fast and loose with terminology, it seems pointless to try to associate "irreducible complexity" with any meaningful proposed formal definition of complexity. But I think there is a good case, intuitively, for thinking of biological or organic complexity as fairly close to what we find in fractal geometry and so forth. That much granted, it is hardly surprising that complexity, in this sense, may be generated by a large number of iterations of a very simple algorithm, specifically, many generations of selection operating on variation.

Call me a cynic, but I don't think any of this will convince anyone who wasn't already convinced -- in taking apart the argument, the assumption is that these people are trying to rationally understand something, so that pointing out the irrationality of it will change their minds. In their corner of the universe, though, these arguments are just "talking points" that people parrot in order to signal membership to a particular club or tribe, much the same way hairstyles and slang or jargon do.

If one argument turns out not to work, they shift the goalposts and conjure up another, and so on, so that attacking their arguments is largely a waste of time.

It strikes me that while it's easy and fun to bandy around Godel, Turing et al in the way that we all did when we first read Douglas Hofstadter back in the day (whatever happened to the Eternal Golden Braid fans? Mandelbrotians?), the only way to show anything in mathematics is to use mathematics.

That's what mathematicians do. While Turing and Godel certainly have philosophical implications (more, I'd wager, than the work of any hundred fellows of the Continental persuasion), the proper way to cook with the fellows is employ their native language with unimpeachable rigour.

So where is the actual maths? ID is sufficiently badly thought of in academia that a proper bit of well-argued mathematical logic would be a gem without price. I have been led to believe that there are qualified mathematicians involved in the movement - doesn't Dembski map onto Isaac Newton through some sort of transform? - so let's see that first and the pop science version afterwards.

The good thing about maths is that you only need brains, a sharp pencil and plenty of paper.

I'm prepared to sponsor the pencil.

R

The revisionist history of von Neumann is wrong, but the conventional history is oversimplied, and thus partially wrong, too. The details of how von Neumann and Stanislaw Ulam invented Cellular Automata, and why, and what von Neumann wanted to do next (shrink the quantized space to continuous space, and the difference equations to differential equation) was something that he bemoaned on his deathbed not having gotten around to doing.

There has been a complicated interplay between simulations, theory, and in vivo (or in vitro) biology for a long time. In a sense, explicating this is best left to the Historians of Science -- except not enough of them have expertise in more than one discipline of science in the first place.

Which came first: Umbarger's 1959 discovery of feedback loops in the dynamics of metabolic systems, or every electrical engineer who ever looked at a metabolic chart and assumed that everyone could see that feedback loops were important? Which came first, Schrodinger's "What is Life" theorizing about "aperiodic 1-dimensional crystals" or Crick and Watson's DNA model? The chronology of publications is clear; the chronology of ideas floating around in scientific bull sessions is another.

The ID folks are wrong here, but we should not be too smug about trotting out the Establishment's Whig History of Science, either.

I think it should be noted that the definition of "complexity" is really up for grabs, and that Kolmogorov-Chaitin complexity, i.e., algorithmic incompressibility, is just one candidate.

Furthermore, apparently there is no procedure for finding all patterns in an entity:

A measure that corresponds much better to what is usually meant by complexity in ordinary conversation, as well as in scientific discourse, refers not to the length of the most concise description of an entity (which is roughly what AIC is), but to the length of a concise description of a set of the entity's regularities. Thus something almost entirely random, with practically no regularities, would have effective complexity near zero. So would something completely regular, such as a bit string consisting entirely of zeroes. Effective complexity can be high only a region intermediate between total order and complete disorder.

There can exist no procedure for finding the set of all regularities of an entity. But classes of regularities can be identified.

(Murray Gell-Mann) [Bold added.] ( http://golem.ph.utexas.edu/category/2006/12/comm... )

Hmm. Analogous to that finite axiomatics perhaps can't find all possible patterns (theorems) according to Gödel, possibly?

But I think there is a good case, intuitively, for thinking of biological or organic complexity as fairly close to what we find in fractal geometry and so forth.

I think that is a striking possibility. All lifes structures (phylogenetic trees, phenomes, genomes) are free to develop on all scales (populations, body structures, gene changes). They are also nonlinearly correlated (competition, constraints, multiplicative effects and feedback).

So they could look like power law distributions in some measures, just as scale invariant structures do. But there are also constraints (granularities), such as generation times and cell sizes, that affects this.

In fact, on Panda's Thumb IIRC some biologist mentioned that measuring DNA for sequence frequency, non-functional junk-DNA roughly follows Zipf's law, expected from power law distributions. While functional DNA, or at least coding DNA, deviates slightly.

So it seems that one can, at least in some cases, identify life's "signature" as modulations on power law distributions. I think that is neat.

As Chad Groft already pointed out: the completeness theorem of Gödel does not state that arithmetic can be described by a finite number of axioms in first order logic. The completeness theorem states that every statement that is true for all models that satisfy a given set of axioms can be proved using first order logic.

The incompleteness theorem on the other hand implies that if you have an axiom system for which arithmetic is a model, there will always be other models that satisfy the same axioms. So in a way Sal's statement that arithmetic is to rich to be contained in a finite number of axioms is correct. The further conclusions he draws from this are of course nonsense.

I think that you should update your post to correct this mistake because in the battle against ID it is important to keep truth and sound reasoning on our side.

So where is the actual maths?

Oh, it's there in all its glory:

Assuming this general software-model the origin-of-life problem can be expressed as: if the inputs are sparse atoms and energy (the so-called primordial "soup"); if the software are all the physical and chemical natural laws and randomness; is the output life itself? Let's express that this way: (atoms + energy) -> (natural laws + randomness) -> life [yes/no?].

This type of information can derive from an intelligent agent only. According to IDT the formula becomes (atoms + energy) -> (intelligence + natural laws) -> life.

Clearly the creationistic model gives yes as a predictive answer, while the evolutionary model can't answer [yes/no?]. Therefore creationist math shows that creationism is correct.

(Dembski is a bit better, but Mark has analyzed some of that before. Essentially Dembski won't state any clear definitions to work from.)

The chronology of publications is clear; the chronology of ideas floating around in scientific bull sessions is another.

I can appreciate that, and I have been floating bull, erhm, ideas, myself. It is actually hard to puzzle together a history without having been present in the area at the time. Unfortunately very few papers have the courage to present the whole work with all the sidesteps and failures that is both educational, saves others time and gives the full history.

So I thought an official chronology would do. As you say, the rest is best left to historians of science. (And even then I would suspect the result. :-)

The date for von Neumann's official start on biologically inspired models where from Wolfram's book. I caveated that, because I didn't took the time to check his sources or reviews on the book. Unfortunately, I forgot the link to his book: http://www.wolframscience.com/reference/notes/876b .

Remaining data is from Wikipedia articles, likewise not checked. (It was a comment, not a post. ;-) What is clear is that the creationist data and dates on DNA and protein production is bull, as is the idea that biologists didn't know about the genome and its rough implementation (alleles and chromosomes) before.

I appreciate your insights into the chronology of ideas; in fact, the Schrödinger crystals feels familiar.

When are some group of mathematicians who follow ID going to contact Chaitin and ask him to comment? Perhaps the outcome will be another aphorism to add to the "written in jello" comment of the discoverer of the NFL theorems regarding Dembski's ramblings.

and gives the full history.

Well, it wouldn't give the full bull history of course. But it would help identify with which ideas where actually tried in some measure.

I'm not generally mathematically educated enough to comment on most of this, so I'll just make a point of semantics here: when he writes "...'enemy' of Darwinism, the biological theory according to which life and species arose without the need of intelligence?", it comes off as even more absurd as usual to use the 'slur' of calling evolution 'Darwinism', since his post is all about genetic coding and DNA (or tries to be), about which Darwin himself had absolutely no idea, of course.

Of course, when I say "even more absurd as usual," I mean "even more absurd than usual." My bad.

So, what would be the minimum description length for the Intelligent Design "Theory"? Well, four letters, of course!

> [...] attacking their arguments is largely a waste of time.

If the objective is to make them realise their mistake, then you're probably right.

However, if the objetive is to learn by figuring out why and where they are wrong, then I think it's not a complete waste of time. Some of their arguments are quite subtle and it takes some understanding to debunk them.

"information is too rich" is an incomplete statement: what information? A statement like that cannot stand on its own. Information can be generated by anything - finite sets of instructions, noise on a telephone line, emissions of a particular wavelength from a star - all produce information.

Hello Mark,

It may be a load of crap or it may not.

It depends on how the person who wrote the paper defines "information". I don't think he made it explicit.

All the things you list above may or not be information depending on how you define the term.

Celal:

All the things you list above may or not be information depending on how you define the term.

In which case their statement is still a load of crap, only for a different reason. Rather than being strictly false (as it is if you assume they're talking about Shannon or KC information), it merely becomes useless words. Science requires strict definition of terms. Math is even stricter. If you simply make some point about a generic and undefined form of 'information', then you aren't doing science or math. You're just wrong.

Mathematical game theory may be a means of working with incomplete information and possibly dealing with the halting problem. This may be particularly true for dynamic noncooperative game theory of infinite games, with continuous time, with or without stochastic influence.

Game theory is applied mathematics often used successfully by various engineers who operate physics applications.

The ArXiv groups game theory with computer programming.
http://arxiv.org/list/cs.GT/06

NATURE - Current issue: Volume 445 Number 7126 pp339-458 has at least three articles that appear to incorporate aspects of game theory. [Probably read the editor's summary first, then the article, if these are found to be of interest.]

1 - Fish can infer social rank by observation alone p429
Logan Gooseneck, Tricia S. Clement and Russell D. Fernald
doi:10.1038/nature05511

2 - 'Infotaxis' as a strategy for searching without gradients p406
Massimo Vergassola, Emmanuel Villermaux and Boris I Shraiman
doi:10.1038/nature05464

3 - Comparison of the Hanbury Brown-Twiss effect [HBTE] for bosons and fermions p402
T Jeltes, ..., CI Westbrook, et al
doi:10.1038/nature05513

Fish observations and "infotaxis" [robotics] appear to be consistent with pursuit-evasion [P-E] games.
These are related to biophysics.

HBTE discusses the social life of atoms: HE-3 fermions and HE-4 bosons display bunching and anti-bunching [or attractor and dissipator] behavior.
Perhaps this type of high energy physics [HEP] may be analyzed via P-E games.

Just keep presuming I won't return or that I'm incapable of seeing the invincible Chu's fumblings.

Well, you have still not visited Mark's post and discussed it.

Nor have you understood the points where Mark may have messed up a bit, or what PG discusses here.

Mark didn't discuss PG's point, that you can always use more powerful formal systems. This is the point you don't get, since you continue to frame your discussion as if we had only one system.

Mark did discuss Gödel's completeness theorem instead. But that is only applicable for formal systems describable with first-order predicate logic, which isn't systems that describes arithmetic.

But all that is besides the point. The main point with this exercise is that creationists can't take Gödel's results to imply that "more doesn't come from less" or that this is about biology.

Obviously Gödel showed that logics could be used to represent and reason about themselves, so more came from less. And the other mathematicians results where in the same vein.

And you can't put limits on biology from limits on formal systems. How would you do that?

In fact, Gödel showed with his theorems that we can always extend formal systems indefinitely (from the completeness theorem) to contain more theorems (describing 'structure') in some more powerful model (from incompleteness theorem II). So if anything, it shows that even so simple things like formal systems have unbounded 'structural' possibilities.

Does that remind you of any special system in the context? A system that with some selection incorporates information from the environment and changes (new 'rules')? And no, I'm not referring to your brain, Sal. It is selective all right, but the information incorporation and the change remains to prove.

the thought that I might have a valid point is intolerable to him.

No, the way you twist and misrepresent math is intolerable to him.

So go and ask him the question you pose here, and see what he will answer. As he is a computer scientist in the lime light, and expert math user to boot, I'm sure you will get an answer that isn't twisted or misrepresented.

Uuups! Sorry, the comment was meant for the http://www.pandasthumb.org/archives/2007/02/disinformation.html thread, where Sal is commenting. Well, he will recognize the post if he comes here.

Raf Bocklandt wrote:

The completeness theorem states that every statement that is true for all models that satisfy a given set of axioms can be proved using first order logic.

So beautifully stated. And then incompleteness happens when we have statements that are true in some models of a set of axioms but not true in other models of the same set of axioms.

As a illustration, we have field axioms. Some examples of models of field axioms the the rationals (Q), the reasl (R), and the complex number (C).

The assertion "There exists an a with a*a = 2" is true in the model of a field known as R but false in model of a field known as Q. Hence, if one calls such an assertion an arithmetic statment, we have shown completeness theorem does not demonstrate all arithmetic statements are provable from the finite set of axioms I started with (in this case I was using field axioms).

Hence I have given a counter example, and shown Mark was fumbling when he asserted:

Bullshit and nonsense! That's an astonishingly bad explanation of Gödel's incompleteness theorem....
You can describe all of arithmetic using a formal system with a finite set of axioms; in fact, Gödel himself proved that, in his completeness theorem.

Unless of course, Mark wants to argue for adding a new axiom each time one comes across a true statement that's unprovable. But such a kluge supports the original thesis by the ID proponents in Italy who said:

In general mathematics is too rich to be derived from a limited number of propositions (what mathematicians name a "formal system").

And this lead to the following insightful observation.

Raf Bocklandt wrote:

So in a way Sal's statement that arithmetic is to rich to be contained in a finite number of axioms is correct.

Exactly. Raf is a very bright individual. But I should not take credit for what my friends in Italy wrote. It was their essay. I merely presented the material.

Hence I have given a counter example, and shown Mark was fumbling when he asserted

Yes, he fumbled, but not nearly as badly as you and your friends. One of the huge differences between us and you folk is that, when one of us makes a mistake, others of us acknowledge it and even correct it. When are you going to correct the numerous egregious mistakes in the drivel you presented?

But such a kluge supports the original thesis by the ID proponents in Italy who said:

In general mathematics is too rich to be derived from a limited number of propositions (what mathematicians name a "formal system").
... But I should not take credit for what my friends in Italy wrote. It was their essay.

In the sense in which this is true, Gödel proved it. Why then, do your friends get any credit? They only get credit for their novel claims -- that Gödel somehow showed that evolution can't happen. Massively negative credit, because it's an incredibly stupid claim.

Raf is a very bright individual.

Since you recognize that, then you must recognize the wisdom of
http://goodmath.blogspot.com/2006/03/king-of-bad-math-dembskis-bad.html

It's time to take a look at one of the most obnoxious duplicitous promoters of Bad Math, William Dembski. I have a deep revulsion for this character, because he's actually a decent mathematician, but he's devoted his skills to creating convincing mathematical arguments based on invalid premises. But he's careful: he does his meticulous best to hide his assumptions under a flurry of mathematical jargon.

But such a kluge supports the original thesis

Which is still inconsequential as I noted above. What you need to do to make something consequential in this vein is to explain where limits on biological systems come from and what they are, not discuss an already corrected point.

The Shannon terminology of "codes", "optimal", "encoding", and "signals" is used in the following press release.

This gets at the subtle notion of evolution by natural selection of the mechanisms for evolution by natural selection. That is, how did the Genetic Algorithm with actual genetic codes manage to improve the performance of actual genetic codes?

My simulations 1974-1977 proved to my satisfaction, and have been cited in published papers, that the Genetic Algorithm need not have an "intelligent" programmer provide optimal mutation rates, for each of several types of mutation. Instead, the string of parameter (simulated chromosome) can have concatenated to it a string of meta-parameters, including mutation rates.

While the population of strings (simulated genome) evolves by the genetic algorithm (simulated evolution by natural selection), the system as a whole evolves to nearly optimal meta-parameters including mutation rates.

This is consistent with John Hollands insight that the genetic algorithm is not only a parallel algorithm, but also parallel at a higher level of abstraction, simultaneously optimizing average height on the fitness landscape, but also optimizing over a super-space of "patterns" or "schema" of much higher dimensionality. For instance, if there are N loci and 2 possible alleles at each locus, then there are 2^N possible chromosomes. But the schema can have 3 values at each locus: 1, 0, or "don't care." Hence there are 3^N schema. That can be much bigger than 2^N as N gets huge.

The actual population is a tiny sample of the superspace of possible shema. Holland proved that the average fitness of schema represented in the population grow exponentially faster as fitness increases, in parallel with the average fitness of strings actually in the population, proportional to fitness of those strings.

I think that, just as I was the first to use Holland's genetic algorithm to evolve useful working programs (in APL) and solutions to previously unsolved problems in the scientific literature, I may have been the first to demonstrate Holland's idea, by evolving the parameters of evolving.

It seems that Life on Earth beat me (and Holland) to the punch by over a billion years. See below.

Of course, I may be misinterpreting the press release; and I haven't yet seen the primary source (actual scientific paper).

http://www.sciencedaily.com/releases/2007/02/070208230116.htm

Source: Cold Spring Harbor Laboratory
Date: February 9, 2007

Scientists Discover Parallel Codes In Genes

Science Daily -- Researchers from The Weizmann Institute of Science report the discovery of two new properties of the genetic code. Their work, which appears online in Genome Research, shows that the genetic code -- used by organisms as diverse as reef coral, termites, and humans -- is nearly optimal for encoding signals of any length in parallel to sequences that code for proteins. In addition, they report that the genetic code is organized so efficiently that when the cellular machinery misses a beat during protein synthesis, the process is promptly halted before energy and resources are wasted.

"Our findings open the possibility that genes can carry additional, currently unknown codes," explains Dr. Uri Alon, principal investigator on the project. "These findings point at possible selection forces that may have shaped the universal genetic code."

The genetic code consists of 61 codons--tri-nucleotide sequences of DNA--that encode 20 amino acids, the building blocks of proteins. In addition, three codons signal the cellular machinery to stop protein synthesis after a full-length protein is built.

While the best-known function of genes is to code for proteins, the DNA sequences of genes also harbor signals for folding, organization, regulation, and splicing. These DNA sequences are typically a bit longer: from four to 150 or more nucleotides in length.

Alon and his doctoral student Shalev Itzkovitz compared the real genetic code to alternative, hypothetical genetic codes with equivalent codon-amino acid assignment characteristics. Remarkably, Itzkovitz and Alon showed that the real genetic code was superior to the vast majority of alternative genetic codes in terms of its ability to encode other information in protein-coding genes--such as splice sites, mRNA secondary structure, or regulatory signals.

Itzkovitz and Alon also demonstrated that the real genetic code provides for the quickest incorporation of a stop signal--compared to most of the alternative genetic codes--in cases where protein synthesis has gone amiss (situations that scientists call "frameshift errors"). This helps the cell to conserve its energy and resources.

"We think that the ability to carry parallel codes--or information beyond the amino acid code--may be a side effect of selection for avoiding aberrant protein synthesis," says Itzkovitz. "These parallel codes were probably exploited during evolution to allow genes to support a wide range of signals to regulate and modify biological processes in cells."

The results of this study will be useful for researchers seeking to identify DNA sequences that regulate the expression and function of the genome. Many currently known regulatory sequences reside in non-protein-coding regions, but this may give scientists incentive to delve deeper into the protein-coding genes in order to solve life's mysteries.

Note: This story has been adapted from a news release issued by Cold Spring Harbor Laboratory.

But the schema can have 3 values at each locus: 1, 0, or "don't care."

"Don't care" meaning neutral fitness (drift) I presume?

Torbjörn Larsson:

Sorry that I didn't explain. My recollection (I don't have John Holland's 1976 book in front of me, or even know where it may be) is as follows.

Suppose that there are two alleles for every gene. That is, the simulated chromosome is a binary string of length N. The population is a fixed-size database of P of these binary strings, each of which has an associated fitness as a real value in the range [0,1].

We are interested in what patterns there are in the population. So we use "don't care" which I will hereafter symbolize as d, as a metacharacter as used in substring searches.

So the set of possible schema (patterns) is {(0,1,d)}^N.

Let's take the small case of N = 3.

Then there are (2^3)-1 = 7 possible chromosomes [correcting my previous claim by 1]:

000, 001, 010, 011, 100, 101, 110, 111

There are (3^3)-1 = 26 possible schema:

000, 00d, 0d0, d00, 0dd, d0d, ddd;
001, 0d1, d01, dd1;
010, 01d, d10, d1d;
011, d11;
100, 10d, 1d0, 1dd;
101, 1d1;
110, 11d;
111.

If there is no "d" in the string, then the pattern is instantiated only by that string. That is, the schema "010" has only the string "010" as an instance.

If there is one d in a schema, then it is instantiated by any string where that d is substituted by either a 0 or a 1.

For example, the string 00d is instantiated by any of the set {000, 001}.

If there is more than one d, again one considers all substitutions.

For example, the string d0d is instantiated by any of the set {000, 001, 100, 101} which is to say anything goes so long as there is a 0 in the middle bit.

Now the number of possible strings can be much larger than the actual simulated population, so there is sampling error in the fitness landscape, which is a kind of "noise" as opposed to mutation, in the channel.

The number of possible schema can be stupendously larger than the number of possible strings.

By the definitions in the model, every possible string has a fitness (technically normalized to a probability).

What is the fitness of a schema?

Holland defines the fitness of a schema to be the mean (average) of the fitness of all instantiations of the schema.

That means our population is also implicitly and in parallel sampling the fitnesses of the schema, at least the ones for which there is at least one instantiation in the population.

Hence there is not only a fitness landscape for the strings, but also a fitness landscape for the schema.

There is a second-order sampling problem here. The remarkable theorem of Holland, which he rigorously defines and provfes, is that evolution by natural selection is implicitly and in parallel going on with the superspace of schema in the larger schema fitness landscape, and that follows the same statistical difference equations (which in the limit become differential equations) that define evolution by natural selection on the population of strings.

This is a very deep and subtle point, which was not understood by a large proportion of readers of Holland's breakthrough book 31 years ago. It may be slightly better grasped today. I do not know how the concept percolated through the biology community. I think (from discussions with him) that the great Leroy Hood got it. Hood was Chairman of Biology at Caltech, lead inveentor of the first DNA sequencer (hence in the National Inventor's Hall of Fame), the first to propose the Human Genome Project, hired away with his whole team by Bill Gates, hence head of the Institute for Systems Biology. ISB does amazing things, but their web site can tell you. Point is, modern Genonmics and Proteomics does huge string-searches at a more sophisticated level than Holland's schema (cf. my earlier discussions of Edit Distance) but Holland led the way.

There is a connection with the Neutral Gene Hypothesis, and with genetic drift, but for the sake of brevity, I'll just say that genetic drift can also be seen as sampling error, and hence "noise" in the channel of evolution by natural selection.

I had an interesting argument for an hour with Dr. George Hockney, which we eventually figured out was because he asssumed that all Genetic Algorithms could be considered to operate on bitstrings (trivially true in software representation, but misleading, as with my evolving of strings of characters which were APL programs) and that the population was infinite, so that the dynamics were described by differential equations (finite population uses difference equations and has sampling error).

Hence my attempts to be very careful in my 80+ page paper on the NECSI wiki, with definitions, context to math, context to information theory and communications theory, and context in actual biology.

hence, also, some of the confusion within Sal, between Sal and commenters at this blog, between we commenters, and within each of our own heads.

Tricky stuff. Good thing that there is a Mathematics community with axiomatic and social reules. Good thing Mark et al teach how one may tell Good Math from Bad Math!

Jonathan Vos Post:

Thank you for your detailed answer!

So we use "don't care" which I will hereafter symbolize as d, as a metacharacter as used in substring searches.

So instead of demoting neutral alleles, it seems to be a choice of a set of dependent alleles. (Perhaps multiplicative or regulatory effects.)

genetic drift can also be seen as sampling error, and hence "noise" in the channel of evolution by natural selection.

I think I see how that would complement the above model, and it is an illuminating idea. That seems to make drift like stochastic processes I am used to, such as Wiener processes. Earlier schematic illustrations of drift that I have seen has not explicitly incorporated noise.

This makes me even more eager to see the finished channel paper.

There's delightful application in calculating entropy in:

http://arxiv.org/pdf/math.GM/0702343
Title: Linguistic-Mathematical Statistics in Rebus, Lyrics, Juridical Texts, Fancies and Paradoxes
Authors: Florentin Smarandache
Comments: 44 pages, many figures. Partially presented at "The Eugene Strens Memorial on Intuitive and Recreational Mathematics and its History", University of Calgary, Alberta, Canada, July 27 - August 2, 1986
Subj-class: General Mathematics
MSC-class: 46N60, 97A20
Journal-ref: Partially published in Review Roumaine de Linguistique, Tome XXVIII, 1983, Cahiers de Linguistique Theorique et Appliquee, Bucharest, Tome XX, 1983, pp. 67-76, Romanian Academy; and other parts of this paper published in various journals

Of course this isn't specifically relevant, but people stumbling on this thread might be interested to learn that dogmatists drawn from the same mold as many of these ID proponents drove Turing to suicide. He was prosecuted for being a homosexual, stripped of the security clearances under which he had done his amazing -- and crucial to the allied victory in the second world war -- cryptography work, and generally ostracized.