This is kind of cool. Koders lets you search perform searches over a repository of many free / open source software projects. You can specify the license and language. For example, a search on "config file parse" with language Tcl and license GPL produces these results.

I've finally gotten around to making the scripts that generate this web site also make an RSS feed.

Guess what's cool? The Internet Problem Solving Contest is cool. Like the ACM International Collegiate Programming Contest and TopCoder, it is a competition focusing on the ability to design and implement non-trivial algorithms quickly. Below are some sample problems to give you an idea of what is involved in this.

• A Tiling Problem from IPSC
• The Problem Set of the 2003 ICPC World Finals

The problems normally take the form of little combinatorial or geometric math puzzles suited to solution techniques such as divide-and-conquer, greedy techniques, or dynamic programming. Such problems are not really representative of real, everyday programming tasks, but they are a fascinating diversion and an excellent mental workout. Developing the ability to solve them quickly is very useful for your mathematical skills.

I was on UW's ICPC team for one year, but I no longer have time to spent on these activities. It's really fun to try solving some of the problems, though; both the IPSC and ICPC have large archives of past problems available on their websites.

Hooray! The act was effectively killed in the Senate Judiciary Committee meeting today. May it never be resurrected.

It's scary just how close we came. The bill isn't just a little bad; it would have radically changed the face of technology. And groups like the RIAA and MPAA almost pushed it through. It just goes to show how vigilant we must be. Their lobbyists have a lot of money, and they are working relentlessly through their pawns such as Senator Orrin Hatch to get technology companies and consumers alike under their control.

If you are not aware of the INDUCE Act currently before the Senate, you should be. If passed, it will essentially overturn the landmark case Sony vs. Universal (known as the Betamax decision), which established the legality of recording devices such as VCR's. Because such devices have legitimate uses, the court ruled that media companies may not hold the device manufacturers liable if someone violates copyright law using them. The INDUCE act reverses this, effectively giving Hollywood the power to shutdown the development and sale of a broad variety of recording and storage devices including VCR's, tape recorders, CD-burners, iPods, and TiVos whenever it desires to do so.

The act does more than give media corporations a tool for fighting piracy; it gives them complete control over any technology that could be used to record audio or video. Opposition to the act in incredibly broad and includes conservative think tank The Heritage Foundation; tech companies including Google, Yahoo, eBay, Intel, and Verizon; the Electronic Frontier Foundation; the NY Times Editorial Board, and a slew of other groups.

How did the act get this far? Media corporation groups such as the RIAA and the MPAA have made major campaign contributions to the Senators that drafted the bill and are its primary supporters. Most in congress have assumed this an issue out of the public eye.

I urge you to call your senator on Tuesday the 14^th, the day selected for everyone to call in order to maximize impact.

The EFF has won Grokster v.s. MGM! This is an exciting, landmark victory for peer-to-peer networks. In short, the ruling means that the people who write peer-to-peer software that runs decentralized networks such as Gnutella cannot be held liable for copyright infringement that takes place on those networks.

The Copyright Owners urge a re-examination of the law in the light of what they believe to be proper public policy, expanding exponentially the reach of the doctrines of contributory and vicarious copyright infringement. Not only would such a renovation conflict with binding precedent, it would be unwise. Doubtless, taking that step would satisfy the Copyright immediate economic aims. However, it would also alter general copyright law in profound ways with unknown ultimate consequences outside the present context.

Further, as we have observed, we live in a quicksilver technological environment with courts ill-suited to fix the flow of internet innovation. AT&T Corp. v. City of Portland, 216 F.3d 871, 876 (9th Cir. 1999). The introduction of new technology is always disruptive to old markets, and particularly to those copyright owners whose works are sold through well established distribution mechanisms. Yet, history has shown that time and market forces often provide equilibrium in balancing interests, whether the new technology be a player piano, a copier, a tape recorder, a video recorder, a personal computer, a karaoke machine, or an MP3 player.Thus, it is prudent for courts to exercise caution before restructuring liability theories for the purpose of addressing specific market abuses, despite their apparent present magnitude.

Indeed, the Supreme Court has admonished us to leave such matters to Congress. In Sony-Betamax, the Court spoke quite clearly about the role of Congress in applying copyright law to new technologies. As the Supreme Court stated in that The direction of Art. I is that Congress shall have the power to promote the progress of science and the useful arts. When, as here, the Constitution is permissive, the sign of how far Congress has chosen to go can come only from 464 U.S. at 456 (quoting Deepsouth Packing Co. v. Laitram Corp., 406 U.S. 518, 530 (1972)).

A paper entitled "One hundred prisoners and a lightbulb" by Stanford mathematicians Paul-Olivier Dehaye, Daniel Ford, and Henry Segerman (whose delightful homepage deserves a discussion of its own and suggests he has spent some quality time with Gödel, Escher, Bach) appeared in the Mathematical Intelligencer. It is available as a preprint here, here, here, and here. In that article, a situation very similar to the two switch puzzle is described.

What is exciting about the paper is the degree to which it clobbers this problem! The authors provide several strategies for the problem, analyzing the expected time until the prisoners are freed for each. The first ends up with a nasty O(n^1/2eⁿ). This is dramatically improved by the second to O(n²). The third has an expected running time of O(n log(n)²), which is probably nearly optimal if not optimal. (In any case, the authors point out that no algorithm can do better than O(n log n).) They then proceed to consider a fascinating array of sixteen variations on the problem, including the formulation of the problem with random visitation times. Each of these is promptly solved. Finally, the authors give their "über-theorem": the prisoners can all reliably send each other messages of arbitrary length. Even more astonishing is the "über-über-theorem" that follows it: this can even occur in the scenario of random visitation times.

I highly recommend the paper. Thanks to Evan Danaher for pointing it out to me. Check out this page in the puzzle section for a little more info.

David Madore has a fantastic page about quines. It is nearly impossible to read it without being deeply educated in the process.

He goes far beyond most pages about quines (such as my own), which explain the basic idea of quines and give several examples. One highlight is his discussion of the fixed point theorem, which is interesting by itself, apart from its relationship with quines. Also cool is the (previously unknown to me) concept of multi-quines. The whole page is littered with many fascinating programs. The fact that he wrote a dc quine ([91PdP93PP10P]91PdP93PP10P) that is nearly identical to one I wrote ([91aPdP93aPp]91aPdP93aPp) warms my heart.

Today I became aware of interesting recent events involving the ACLU, the Department of Justice, and the Patriot Act.

Apparently, the ACLU is challenging the "National Security Letters" provision of the Patriot Act [link], which allows the FBI to order telephone companies, Internet service providers, banks, credit bureaus, and other businesses to produce records about their customers without a court order or the approval of a judge. The FBI was already capable of exercising this power prior to the Patriot Act, but only against suspected terrorists and foreign spies. The Patriot Act, however, removes restrictions on the use of this authority, and the ACLU alleges that the FBI can now use this power to obtain information about any citizen, for any reason, without providing a justification.

Now here's where it gets interesting. The Patriot Act also includes measures that shroud uses of National Security Letters in secrecy. If a company is served a National Security Letter and required to turn over its customer records, the company is compelled by a permanent gag order to not reveal that this has occurred! These secrecy requirements also (somehow) prevented the ACLU from revealing that they were filing a lawsuit to challenge the measures. Several weeks ago, the ACLU managed to win a special exception that allowed them to reveal the existence of the legal challenge [link] (that's why we now know that any of this is going on at all). When this occurred, the ACLU posted a press release about the case.

The next day, however, the ACLU was forced by the court to remove two paragraphs from the webpage with the press release [link]. One was simply some court briefing schedule. The other, however, was the following, according to the Washington Post.

The provision under challenge allows an FBI agent to write a letter demanding the disclosure of the name, screen names, addresses, e-mail header information, and other sensitive information held by 'electronic communication service providers.'

What? The types of information that the FBI can order disclosed are a secret? I tell you, it just gets creepier and creepier. Not only are uses of these National Security Letters kept secret, but the specific powers they grant to the FBI are now apparently secret!

Update:
The ACLU has since succeeded in striking down the National Security Letters provision of the Patriot Act as unconstitutional. Yay to the ACLU, the courts, and the constitution! Federal judge Victor Marrero, who issued the ruling, had strong words criticizing the provision stating, "democracy abhors undue secrecy".

I just got a US Cellular cell phone. They have a service you can pay extra for that gives you an email address that forwards emails as SMS messages to your phone. However, you can easily roll your own using their web SMS sending form. I wrote a script to send messages via that form. Then I wrote a procmail recipe to forward any messages with the subject "SMS":

:0
* ^Subject: SMS
| ~bethenco/bin/usc-sms --email 6084388810

There you have it! Email to SMS forwarding for free.

Feel free to test this out by sending me an email with the subject "SMS"; I get a little thrill every time this system works. I won't reply, though, as I have to pay to send SMS messages.

I just finished reading this book. I really enjoyed it and recommend it if you have interests similar to mine. It chronicles the development of mathematical logic, especially as it relates to computers. The characters include Boole, Cantor, Gödel, Turing, and others. This is the area of mathematics I find most interesting.

When I first became an undergraduate here at UW, I entered in the computer engineering program rather than the computer science program, where my interests now primarily lie. In retrospect, I think what I really wanted to do was the sort of thing the people in the later parts of this book did. I soon realized, however, that the fundamental ideas of computers have long since been very thoroughly invented, and nobody was doing the sort of thing I wanted to do anymore. The overall organization and design of computers hasn't really changed since the time of Turing and von Nuemann; the implementation has just become more complicated as we push for more performance.

Read the Hacks Memo. I can't think of any activity more edifying than pondering an entry in HAKMEM, coding things up here and there, and proving a lemma. This is what it is all about.

If you haven't seen this document before, you're in for a real treat! It is a file that was passed around the MIT AI lab in the 70's by such characters as Marvin Minsky, Richard Stallman, Bill Gosper, and Gerald Sussman. It is an informal list of problems and trivia relating to math and computers.

Here are some free samples to pique your interest.

ITEM 33 (Schroeppel): Russian doll primes
Numbers whose right digit can be repeatedly removed and they are still prime: CONJECTURE: There are a finite number of them in any radix. In decimal there are 51, the longest being 1,979,339,333 and 1,979,339,339.

ITEM 149 (Minsky): CIRCLE ALGORITHM
Here is an elegant way to draw almost circles on a point-plotting display:

NEW X = OLD X - epsilon * OLD Y
NEW Y = OLD Y + epsilon * NEW(!) X

This makes a very round ellipse centered at the origin with its size determined by the initial point. epsilon determines the angular velocity of the circulating point, and slightly affects the eccentricity. If epsilon is a power of 2, then we don't even need multiplication, let alone square roots, sines, and cosines! The "circle" will be perfectly stable because the points soon become periodic.

The circle algorithm was invented by mistake when I tried to save one register in a display hack! Ben Gurley had an amazing display hack using only about six or seven instructions, and it was a great wonder. But it was basically line-oriented. It occurred to me that it would be exciting to have curves, and I was trying to get a curve display hack with minimal instructions.

ITEM 102 (Schroeppel): Group-like definitions
As opposed to the usual formulation of a group, where you are given

1. there exists an I such that A * I = I * A = A, and
2. for all A, B and C, (A * B) * C = A * (B * C), and
3. for each A there exists an A' such that A * A' = A' * A = I, and
4. sometimes you are given that I and A' are unique.

If instead you are given A * I = A and A * A' = I, then the above rules can be derived. But if you are given A * I = A and A' * A = I, then something very much like a group, but not necessarily a group, results. For example, every element is duplicated.

It looks like Cory Doctorow has written another book. It's been out for several months, but it somehow slipped under my radar until now. I'll have to check this one out.

Cory Doctorow is pretty slick. He works for the EFF, has released two novels online under Creative Commons licenses, and is among the editors of the greatly linked (even more so now) Boing Boing.

I really liked Down and Out in the Magic Kingdom. As I recall, I had been thinking along the lines of the book with respect to wuffie and so forth for some time before I read it. When I read it, I was very excited that other people were having ideas similar to mine. For some reason it feels wonderfully validating when your ideas mirror those of the collective consciousness.

It's interesting how many inventions are disputed because people tend to independently come up with the same idea at the same time. I suppose this happens when the technological and cultural state of the world becomes ripe for a particular idea. It is nice to think of this situation as the culture in general coming up with the idea rather than any particular person.

I think the previous paragraph gives a hint to why I take a weaker view of intellectual property than many people (that is to say, ideas seem less ownable to me). Some things are very clearly ownable. If someone walks out into the middle of nowhere, plants some apple seeds, waters the tree for a few years, then plucks an apple from it, everyone would agree that they, and no one else, own that apple. But the creation of intellectual "property" does not really occur like this. Ideas do not develop in isolation. The situation with cultural and technological developments is much more akin to one person planting some apple seeds, hundreds of others watering the tree, and another person picking the apple.

God, this must be the most rambling blog entry ever. And that's saying a lot.

So the other day I was invited to join Orkut, a friendster-like social networking site. I have mixed feelings about it.

There is a grumpy part of me that despises Orkut, Livejournal, instant messaging, and other such things as frilly nonsense. "Oh look! I have 58 friends in my friendnet and I'm a member of 37 communities! Look at all the funny avatars in my buddy list! Let me go peruse the pointless crap all my online friends post in their fotoblogs!"

Bah. Humbug. I'm trying to get rid of friends here, not increase the efficiency with which they waste my time. This is why I hate instant messaging so much. I sit down at my computer, ready to do some programming, and someone starts talking to me! And they never have something they actually need to say either. All instant messaging conversations are worthless chatter. That's why I never run instant messaging clients anymore.

But then there is another side to me that isn't so grumpy. When someone invited me to join Orkut, this side was very curious. Once I joined, I began to think that it was actually really neat. It's fun to see the friends of your friends and explore these networks. Before I knew it I was trying to add as many people to my list of friends as possible.

Practically every day now I go to Orkut and see how the network around me is developing. And every time I do this, the grumpy part of me gets very embarrassed because it has to share a body with such a pansy.

Yesterday afternoon I got really fascinated with the Look and Say sequence of integers and wrote a program to generate them.

I talked with Russ (from the graphics lab, which is more or less adjacent to the UPL) about this sequence last night. The chaotic nature of the Look and Say sequence reminded him of the Collatz Problem, which may be stated as follows. Let a₀ be a positive integer. Let a_n+1 be 3a_n + 1 if a_n is odd, or a_n / 2 if a_n is even. The question is then "Does the sequence a_n always eventually reach 1, regardless of the choice of a₀?".

If such a sequence ever does reach one, then it goes into the cycle 1 4 2 1. All starting values have been tried up to about 10¹⁶ and found to indeed eventually arrive at one. If some starting value never arrives at one, then that would mean that either there is a sequence that increases indefinitely or there is a cycle other than the one just mentioned.

Whether all starting values arrive at one is unknown, despite extensive efforts. The problem has proven very difficult. Paul Erdos said of the problem, "mathematics is not yet ready for such problems". It seems that we have very few tools for understanding chaotic things.

To brighten your day, here is some funky algebra that shows a strange fact. First we define x. Then we multiply both sides of the equation by the continued fraction (distributing on the right). Then we substitute x in twice. Next we rearrange. Then we take the square root of both sides. Then we substitute x into the right hand side over and over. Finally we substitute the continued fraction for x.

Some of you may be wondering why my website hasn't been updated for over a month. (Humor me. You were wondering, ok?)

I have been rewriting all the scripts that generate these pages. If you ever looked at the old html, you know that it was a horrible mess. With my new Professional Web Developer skills, I fixed it up. Now all the pages are valid XHTML 1.0 Strict (theoretically; if you notice otherwise please let me know) and there are no tables (except to present content which is actually tabular). All the layout is done with validated CSS.

I have yet to reimplement the RSS feeds, but I'm too sick of mucking around with webpages to do it now. The blog-crawling bots that account for the vast majority of my traffic will be sorely disappointed. Disappointed in that cute robot way.

TouchGraph GoogleBrowser is a slick Java applet that combines an interactive graph layout engine with the graph of web pages defined by Google's 'related pages' feature. You enter an initial URL, and the applet fetches some related pages and adds them as nodes in the new graph. Then you can double click on nodes to find pages related to those nodes, and so on. It's really very interesting.

"What you get when you run mathematics through a disassembler." - Michael Schaeffer

I recently ran across a really cool website: metamath.org. Here's the site's description of itself:

Metamath is a tiny language that can express theorems in abstract mathematics, accompanied by proofs that can be verified by a computer program. This site has a collection of web pages generated from those proofs and lets you see mathematics developed formally from first principles with absolute rigor. Hopefully it will amuse you, amaze you, and possibly enlighten you in its own special way.

The `symbol-pushing' part of mathematics has always appealed to me. I've often fantasized about deriving definitions from an absolutely minimal core and then creating an enormous database of theorems, all of which can be reduced to a sequence of typographic manipulations of axioms. That's exactly what this site does. The only fundamental symbols in the language of Metamath are the following:

• (arrow): implies
• (sideways backwards L): not
• (upside down A): for all
• (equals sign): equals
• (stylized epsilon): is an element of
• and (left and right parentheses)

All other symbols are simply shorthand notation for these. At the site, you can explore a database of thousands of theorems that result from various sets of axioms: propositional calculus, predicate calculus, and Zermelo-Fraenkel set theory with the axiom of choice.

What really makes Norman Megill (the creator) such a great guy is the fact that you can download the GPL'd source for the software used to build and verify the proofs in the Metamath language. Also available are a complete tarball of the entire site and a GFDL'd book about meta-mathematics and the Metamath software (with TeX source).

Seriously, folks, this site is one of the coolest things I've seen in a long time. If you enjoy formal systems, this site will make you very happy. On a random note, the website also has a page about converting the proofs to musical compositions.

Today the MyDoom worm began its DDOS on www.sco.com. It's been very successful; unless someone has an idea for a clever solution their web site could be offline for weeks. What if a worm was to base its DDOS target on google results? I'm imagining a really persistent worm that lingers indefinitely in small quantities on the machines of people who don't bother with maintenance. Rather than targeting a specific URL, the worm would attack the top few google results for a particular keyword. Then if the target set up a new web site, it would also be targeted. The worm would tend to silence any discussion of the target as well. Just a thought.

I've decided to start a nice little collection of puzzles, paradoxes, and problems. I love puzzles and frequently run across ones that pique my interest, so now I have a place to collect them. I'll only put puzzles there if I find them sufficiently interesting. You will not find any puzzles there that involve cheap tricks or plays on words, because I hate those. You will also not find any word, letter, or language based puzzles (like crossword puzzles), because I hate those too.

So far, the page contains four items (although one is a repeat of a post on this page).

If you know of any puzzles you think I might like, let me know.

I've added a page about freely available electronic books that I find interesting.