Around here we prefer range voting to approval voting or IRV.

This post on the CACM Blog caught my eye and shows that we still have a long way to go before computing is taken seriously in US secondary education, let alone K-12.

AP CS no Longer Counts for High School Graduation in Georgia (for now)

“Up until September, Georgia and Texas were the (only) two states in the US that accepted a computer science course as fulfilling high school graduation requirements. In Texas, the Advanced Placement Computer Science (AP CS) course fulfilled a mathematics requirement. In Georgia, it fulfilled a fourth science course requirement. As of October, however, Georgia has rescinded that decision. … ”

I wonder how other countries treat computing and informatics in primary and secondary education.

Gregory Chaitin is on tour promoting his new field – metabiology. As Chaitin conceives it, metabiology is the study of the evolution of computer programs, with the goal of proving theorems concerning the circumstances under which evolution occurs. It’s ultimate goal, as the name suggests, is proving that under Earth-like conditions, DNA-based computers must evolve.

Key to Chaitin’s notion of evolution is something he calls creativity, and he explored this idea a little bit in a talk at the University of Toronto’s Centre for Mathematical Medicine. To understand his first theorems in this area, you need to (roughly) understand the Busy Beaver problem of Tibor Rado. A good precis is here. Essentially, a busy beaver is a Turing machine that operates as long as possible, and then halts. The Busy Beaver function, BB(n), is the highest whole number produced by an n-bit busy beaver.

So, to Chaitin’s first theorem in metabiology …

He begins with a single organism – a Turing machine. He mutates this organism, and then either keeps the original and throws away the mutant, or vise-versa, depending on which is more fit. The fitness function is based on the Busy Beaver problem. If the mutant halts, and, upon halting, produces a higher whole number than the original, then the mutant wins. If not, it loses.

Now, BB(n) is uncomputable. In fact, it has no computable bound. Nevertheless, Chaitin shows that random mutations will, in exponential time (on the number of bits, n, in the organism), result in the computation of the Busy Beaver function for n!
(That was an exclamation point, not a factorial sign.)

In other words, evolution causes fitness to increase faster than any computable function. Chaitin calls this “evidence of biological creativity”. This is a nice result, but is one that Chaitin finds less than satisfactory. In real life evolution is cumulative, while Chaitin’s proof requires assuming that evolution sometimes starts over from scratch. He really wants to prove an evolutionary process that is, in some sense, cumulative, in addition to being creative. His second theorem uses his infamous halting probability, Ω, to construct a cumulative path through program space to arbitrary levels of complexity. But this also doesn’t satisfy Chaitin, since the process is unstable, in a sense that he didn’t really explain.

Beyond these two theorems, the field is open. Things to work on seem to be:

i. Without changing the model, can Chaitin’s desired result (cumulative evolution) be proved?

ii. Part of the utility of Chaitin’s fitness function is that it explicitly rewards complexity. This fits with the observation that life, in general, evolves to become more complex. But complexity is, I think, typically seen as an epiphenomenon of fitness, and not as the very definition of fitness. Can a “Darwinian” fitness function be chosen such that complexity is not explicitly rewarded AND such that life can be proven to evolve to arbitrary complexity?

iii. Once we exhaust the limits of what we can prove without an environment, what happens when we introduce an environment, which interacts with the organism, exchanges information with the organism, and which can change, suddenly or gradually?

Of course, (iii) might not be necessary. If (ii) can be proven, then, in a sense, case closed: life must evolve. Some might even say that (ii) isn’t necessary.

But I suspect that Chaitin expects (i) to be very hard. Hence his enthusiasm. In fact, I suspect that he suspects that Ω in going to be all over metabiology, and that some of its fundamental questions will prove to be (mathematically) unknowable.

But algorithmic information theory (AIT) is only one extra-biological approach to evolution. Another is thermodynamics. Eric Chaisson, for example, argues that the Earth, bathed in solar radiation, has a natural tendency towards lower entropy and higher complexity. Is an AIT/Thermodynamics synthesis possible? Google says: Yes, (and it’s been around a while).

The NYT reviewed Logicomix by writer Apostolos Doxiadis and Berkeley CS professor Christos Papadimitriou.

“First published last year in Greece (where it became a surprise best seller), the comic book — er, graphic novel? — is the brainchild of Apostolos Doxiadis, previously the author of a not-bad mathematical fiction called “Uncle Petros and Goldbach’s Conjecture.” For expert assistance on logic, Doxiadis called on his friend Christos Papadimitriou, a professor of computer science at Berkeley and the author of a novel about Alan Turing.”

It looks great. Amazon is out of stock for the harccover version, but there are other online sources that have copies and I’ve ordered one for the ebiquity lab. The paperback version will be released on Monday.

Here’s how the Logicomix site describes it.

“Covering a span of sixty years, the graphic novel Logicomix was inspired by the epic story of the quest for the Foundations of Mathematics.

This was a heroic intellectual adventure most of whose protagonists paid the price of knowledge with extreme personal suffering and even insanity. The book tells its tale in an engaging way, at the same time complex and accessible. It grounds the philosophical struggles on the undercurrent of personal emotional turmoil, as well as the momentous historical events and ideological battles which gave rise to them.

The role of narrator is given to the most eloquent and spirited of the story’s protagonists, the great logician, philosopher and pacifist Bertrand Russell. It is through his eyes that the plights of such great thinkers as Frege, Hilbert, Poincaré, Wittgenstein and Gödel come to life, and through his own passionate involvement in the quest that the various narrative strands come together.”

It looks like the release of Conrad Barski’s long awaited graphic text on Lisp is getting closer. You can now order it from Amazon, although the publication date is listed as April 28, 2010. Conrad’s site says that it’s “due out this Fall” and the publisher’s site says “Coming March 2010″. I hope we don’t have to wait until next Spring.

Conrad Barski, Land of Lisp: Learn to Program in Lisp, One Game at a Time!, No Starch Press, 2010.

Here’s the description from the publisher’s site.

“Lisp is a uniquely powerful programming language that, despite its academic reputation, is actually very practical. Land of Lisp brings the language into the real world, teaching Lisp by showing you how to write several complete Lisp-based games, including a text adventure, an evolution simulation, and a robot battle. While building these games, you’ll learn the core concepts of Lisp programming, such as data types, recursion, input/output, object-oriented programming, and macros. And thanks to the power of Lisp, the code is short. Rather than bogging things down with reference information that is easily found online, Land of Lisp focuses on using Lisp for real programming. While not a cartoon guide like our Manga Guides, the book is filled with author Conrad Barski’s brilliant Lisp cartoons (featuring a Lisp alien and other characters) that are sure to appeal to many Lisp fans and, in the tradition of all No Starch Press titles, make the learning more fun.”

For more information, see the comments on Hacker News.

Botprize is yet another variation on the classic Turing Test. Does setting the evaluation in the context of a online multi-user video game really change the nature of the test? At least this does have real practical values. The computer game industry is very competitive and having more realistic and interesting computer-controlled entities make a game more successful. Technology Review has a short story, A Turing Test for Computer Game Bots on the contest.

“A new contest could help develop better AI for games and other applications.

Can a computer fool expert gamers into believing it’s one of them? That was the question posed at the second annual BotPrize, a three-month contest that concluded today at the IEEE Computational Symposium on Intelligence and Games in Milan.

The contest challenges programmers to create a software “bot” to control a game character that can pass for human, as judged by a panel of experts. The goal is not only to improve AI in entertainment, but also to fuel advances in non-gaming applications of AI.

The contest has been completed, but the results have not yet been announced. The BotPrize web site currently says:

The 2009 BotPrize Contest has been decided!

Complete results will be posted soon, but here is a summary of the results:

None of the bots was able to fool enough judges to take the major prize. But all the bots fooled at least one of the judges.

The most human-like bot was sqlitebot by Jeremy Cothran. The joint runners up were anubot from Chris Pelling and ICE-2009 from the team from Ritsumeikan University, Japan. Jeremy and Chris are both new entrants, and the ICE team were also runners up in 2008.

… more details to follow in the next 24 hours.

Contestants created bots for Unreal Tournament 2004 which communicate with the game server via the GameBots interface.

The TR story continues.

“This year’s BotPrize drew 15 entrants from Japan, the United Kingdom, the United States, Italy, Spain, Brazil, and Canada. Entrants created bots for Unreal Tournament 2004, a first-person shoot-’em-up in which gamers compete against each other for the most virtual kills. For the contest, in-game chatting was disabled so that bots could be evaluated for their so-called “humanness” by “physical” behavior alone. And, to elicit more spontaneity, contestants were given weapons that behaved differently from the ones ordinarily used in the game.

Each expert judge on the prize panel took turns shooting against two unidentified opponents-one human-controlled, the other a bot created by a contestant. After 10 to 15 minutes, the judge tried to identify the AI. To win the big prize, worth $6,000, a bot had to fool at least 80% of the judges. As in last year’s competition, however, none of the participants was able to pull off this feat. A minor award worth $1,700, for the most “human-like” bot, was awarded to Jeremy Cathran, from the University of Southern California, for his entry, called sqlitebo.”

Yesterday’s Chronicle of Education had an article on 5 College Majors On the Rise. It’s gratifying to see that three of them are relevant to IT and computing: service science, health informatics, and computational science. Of course, now is a difficult time for universities and Departments to mount new majors or even tracks. Most schools in the US have had two years of budget cuts due to the recession and/or decline in their endowments. But this is a positive sign for the computing disciplines, which had suffered declines in enrollments after the dot com bubble burst seven years ago.

Maybe WebFinger will succeed where others have failed. At what? At providing a simple handle for a person that can be easily used to get basic information that the person wants to make available. The WebFinger proposal is to use an email address as the handle.

WebFinger, aka Personal Web Discovery. i.e. We’re bringing back the finger protocol, but using HTTP this time.

Techcrunch has a post on this, Google Points At WebFinger. Your Gmail Address Could Soon Be Your ID with some background.

There’s some excitement around the web today among a certain group of high profile techies. What are they so excited about? Something called WebFinger, and the fact that Google is apparently getting serious about supporting it. So what is it?

It’s an extension of something called the “finger protocol” that was used in the earlier days of the web to identify people by their email addresses. As the web expanded, the finger protocol faded out, but the idea of needing a unified way to identify yourself has not. That’s why you keep hearing about OpenID and the like all the time.

The current focus of the WebFinger group is on developing the spec for accessing a user’s metadata given their handle. Using RDF and the FOAF vocabulary should be a no-brainer for representing the metadata.

It will be interesting to see what comes from today’s DDOS attacks on twitter, facebook and liveJournal. It is certainly a show of strength from whoever controls the botnets that launched the attacks. We can only assume that three three are from the same source or at lease related sources. Some sources:

• Official twitter status
• Official twitter blog
• Wired: Facebook Confirms Denial-of-Service Attack
• Techcrunch
• NTY Bits blog
• ComputerWorld

Was it a test? Demonstration? Preparation for extortion (Nice little Internet you got there. Shame if something happened to it.)?

Update 16:45: Here’s a graph from Arbor Networks (via NYT) showing a dramatic drop in traffic this morning.

The perfect document preparation system has yet to be invented, and I’ve tried many over the years, starting with TJ6. It’s surely impossible for any one system to be best, given the range of documents most of us have to produce: letters, memos, resumes, scientic papers, dissertations, books, etc. Microsoft Word is great for many of these, but like many, I’ve concluded that LaTeX is still the best for academic papers or large, complex documents. I think this graph attributed to Marko Pinteric says it elegantly.

That LaTeX is so widely used is remarkable, given that it has been more that 25 years since it was first released and it was based on the somewhat arcane Tex. But LaTeX has its problems too, and one of them is remembering all of the commands to generate the many symbols that we like to use to make out papers seem more profound.

Detexify is a neat Web service that lets you draw a mathematical symbol with your mouse, interprets the result, and shows you what LaTeX command to use to generate it.

It works pretty well! You can look at the source code — mostly in ruby — on github and contribute. Or you can volunteer to help train the system on new symbols.

(via Hacker News)