In light of [my recent demolition of a purported improvement on the second law of thermodynamics][2l], an alert reader sent me [a link to this really boneheaded piece of work at Uncommon Descent by Granville Sewell][sewell].
[sewell]: http://www.uncommondescent.com/intelligent-design/introducing-sewells-law/
[2l]: http://scienceblogs.com/goodmath/2007/06/dembskis_buddy_part_2_murphys.php
Sewell is, yet again, trying to find some way of formulating IDist anti-evolution garbage in terms of the second law of evolution. Sewell’s been doing this for ages, and it’s been a
wretched failure. Naturally, according to Sewell that has *nothing* to do with the fact that his argument is a pile of rubbish – it’s all because people have been distracted by
arguments that came about because people don’t understand the second law of thermodynamics. It’s their confusion of 2LOT, *not* any flaw in Sewell’s argument.
So, he’s proposing a new law which he claims subsumes the 2LOT, and which he modestly names after himself:
Get out your crayons: it's graph coloring time!
One kind of graph problem that’s extremely widely used in computer science is called graph coloring. There’s two versions of it, *vertex coloring*, and *face coloring*.
Vertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they’re assigned different colors?
The variants of the vertex coloring problem are things like:
* What’s the *minimum* number of colors (aka the *chromatic number* of the graph)
that can be used to color a graph?
* Given an integer N, can you find an N-coloring of the graph?
The face coloring problem is more complicated to describe. Suppose you have a *planar* graph. (Remember that that means a graph which can be drawn on a plane with no edges crossing.) Suppose further that the graph has the property that from any vertex v, there is a path through the graph from v to v. Then that graph is called a *map*. For a map drawn on a plane, every edge is part of at least one cycle. The smallest possible cycles – that is, the cycles which are not bisected by any other edges of the graph – are called *countries* or *faces* of the graph. The face coloring problem assigns colors to the *faces* of a graph, so that no two faces that share an edge are the same color. There’s an extremely fascinating proof that any planar map can be face-colored with no more than four colors. We’ll talk about later – it’s the first computer assisted proof that I’m aware of.
Wonderful Mobius Transformation Video
Via The Art of Problem-Solving, a great video on Mobius transformations. I never really got how the inversion transformation fit in with the others before seeing this!
Basic Graphs
Let’s talk a bit about graphs, being a tad more formal about them.
The First Graph Theory Problem
Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreirós book; between that, and a new copy of Quine, I should be OK. But in the meantime, we’ll look at something else. Since I mentioned graph theory on friday, and I’ve been promising forever to write about it, I figured this is a good time.
My favorite introduction to graph theory is stolen from one of my grad school professors. It’s the first major use of what became graph theory, which is a proof by Euler.
Here’s the problem. Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it’s got parts of the city on the banks of the river, and parts on two islands. To get around
the city, there were seven bridges connecting the parts of the city. Is it possible to
take a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it’s possible to tour the city crossing each bridge exactly once?
PZ Has a Question: Is George Gilder Wrong About Network Theory?
PZ wrote about the latest nonsense from IDiot George Gilder. In this interview, Gilder tries to make some really horrible arguments about how everything is really hierarchical, and he uses “information theory, computer science, and network theory” as examples.
I believe that the universe is hierarchical, with creation at the top – the idea that there’s a creator and that we, at our best, act in his image. This top-down model is what all of my work has in common. I sensed that the basic flaw and failure of feminism was its gradient toward pure animal passion with no procreative purpose. In economics, I believed that it was the supply that created the demand. In my examination of computers and telecom, and subsequently biology, I saw the same thing. That’s really how I came into the intelligent design movement – through the recognition of this same structure that I’d previously examined in sexuality and economics, information theory, computer science and network theory.
PZ does a great job of tearing him down, but also asks:
Computer science and network theory: Gilder knows nothing about either, and has no training in the subjects. I suspect there are readers who know far more about the subject than Gilder: is network theory all about setting up strict hierarchies of top-down control?
And hey golly, that’s right smack dab in my area.
Network theory is seriously nifty stuff. It’s a sub-area of graph theory, which is one
of my favorite areas of computer science. And the short answer to PZs question is: “Hell no: in fact, if that *were* the case, it wouldn’t be an interesting subject at all. What makes it so interesting and difficult is precisely the fact that things aren’t hierarchical”.
Simple Pathology: Betterave
Sorry for the missed weeks of friday pathological programming language columns. To be honest, I’m running out of languages. I’m sure there must be more, but my usual sources (dealers?) are running out – so send links!
Anyway, today I’m going to look at a really simple one, which I find fun. It’s
not an overly exciting language, but it is a language which is has semantics almost as
trivially simple as [BrainFuck][bf], but which ends up looking almost as much like line-noise as [TECO][teco]. It’s called [Betterave][betterave].
[betterave]: http://www.esolangs.org/wiki/Betterave
[teco]: http://scienceblogs.com/goodmath/2006/09/worlds_greatest_pathological_l_1.php
[bf]: http://scienceblogs.com/goodmath/2006/07/gmbm_friday_pathological_progr.php
Alternative Axioms: NBG Set Theory
So far, we’ve been talking mainly about the ZFC axiomatization of set theory, but in fact, when I’ve talked about classes, I’ve really been talking about the von Newmann-Bernays-Gödel definition of classes. (For example, the proof I showed the other day that the ordinals are a proper class is an NBG proof.) NBG is an alternate formulation of set theory which has the same proof power as ZFC, but does it with a finite set of axioms. (If you recall, several of the axioms of ZFC are actually axiom schemas, which need to be distinctly instantiated for all possible predicates.) NBG uses one axiom scheme, but it’s possible to show that that schema only expands into a finite number of distinct axioms.
Dembski's Buddy (part 2): Murphy's Law and Poincare Recurrence
Part two of our crackpot’s babblings are actually more interesting in their way, because they touch on a fascinating mathematical issue, which, unfortunately, Mr. Brookfield is compeletely unable to understand: the Poincare recurrence theorem.
Brookfield argues that the second law of thermodynamics in not really a law, since it’s statistical, and that there must therefore be some real law underlying the statistical behavior normally explained by the second law. Here’s his version – be prepared to giggle:
“The second law of thermodynamics has a rather different status than that of other laws
of science, such as Newton’s law of gravity, for example, because it does not hold
always, just in the vast majority of cases.”Well, if it is a “law” then it must hold always by definition. If it “does not hold always”
then it is not a law, period. If it is a “pseudo law” then that is fine for pseudo science, but
I am not interested in doing pseudo science. Hawking says that the thermodynamic arrow
is reversible because..“…The probability of all the gas molecules in a box being found in one half of the box at
a later time is many millions of millions to one, but it can happen.”The type of event that Hawking is referring to here is known as “Poincaré Recurrence”–
named after the French mathematician Henri Poincaré. The result of any such occurrence
will indeed reverse the thermal characteristics of the box contents, violating the internal
thermodynamic arrow. This internal reversal however will not (in my opinion) reverse
the real arrow — the unrelenting order to disorder movement of the total physical system.
Yes, folks – Brookfield is a real scientist, doing real science; Steven Hawkings and his ilk are all just pseudo-scientists studying psuedo-laws; real scientists like Brookfield throw out hopeless pseudo-laws like the second law of thermodynamics in favor of Murphy’s law. And yes, that Murphy’s law. Brookfield really tries to argue for the use of Murphy’s law as a better statement of the principle of the second law. But we’ll get to that later.
The Work of Bill Demski's New Best Buddy: The Law of Devolution (part 1)
As several of my fellow science-bloggers pointed out, William Dembski has written a post at Uncommon Descent extolling an “international coalition of non-religious ID scientists“, and wondering how us nasty darwinists are going to deal with them.
Alas for poor Bill. I’m forced to wonder: is there any purported ID scholar so stupid that Bill won’t endorse them? In his eagerness to embrace anyone who supports ID, he didn’t both to actually check who or what he was referencing. This “international coalition” turns out to be a lone uneducated crackpot from Canada who uses his ID beliefs as a justification for running on online sex-toys shop! Several people have written about the organization; I decided to take a look at the “science” that it/he published, in the form of a sloppy paper called “In Search of a Cosmic Super-Law: The Supreme “Second Law” of Devolution“.