Language models are widely used in processing both written and spoken language. They are used for part of speech tagging, sense tagging, disambiguation, text similarity metrics, and many other tasks, including predicting the words a person intends when typing on a telephone keypad. The last application has some interesting wrinkles, as this video we spotted on Language Log explains.

The most popular predictive text system in use today is T9, developed by Nuance Communications. You can check out the video’s examples using this T9 demo.

I think our nervous systems must be wired up a bit strangely.

Screedbot is an “animated scrolling typewriter text generator” service. You enter some text, click CREATE SCREED and get an animated gif image. You can define the width, font size and colors of your screed.. Screedbot was written by Zach Beane in Common Lisp. (Spotted on Lemonodor).

I just discovered (via del.icio.us/polular) an extraordinary proof of the halting problem by linguist Geoffrey Pullum, now at the University of Edinburgh. What’s unusual about it is that it’s written as a poem in the style of Dr. Seuss.

Geoffrey K. Pullum, Scooping the loop snooper: An elementary proof of the undecidability of the halting problem. Mathematics Magazine 73.4 (October 2000), 319-320.

It’s a marvelous proof, sure to liven up any undergraduate theory of computation class. But I noticed errors in the proof — not logical errors, but a transcriptional ones in the form of a mangled word, perhaps introduced by an OCR system. The third line of the fifth stanza reads “that would take and program and call P (of course!)” which has problems in syntax, semantics, rhythm and meter. I’d guess it should be “that would take any program and call P (of course!)”. Similarly, “the” in the third line in the third stanza should probably be “they”. Most of the online version I found had these errors, but I eventually found what I take to be a correct version on the QED blog. I’ve not been able to get to the original version in Mathematical Magazine to verify the corrected version which I include below.

No program can say what another will do.
Now, I won’t just assert that, I’ll prove it to you:
I will prove that although you might work til you drop,
you can’t predict whether a program will stop.

Imagine we have a procedure called P
that will snoop in the source code of programs to see
there aren’t infinite loops that go round and around;
and P prints the word “Fine!” if no looping is found.

You feed in your code, and the input it needs,
and then P takes them both and it studies and reads
and computes whether things will all end as they should
(as opposed to going loopy the way that they could).

Well, the truth is that P cannot possibly be,
because if you wrote it and gave it to me,
I could use it to set up a logical bind
that would shatter your reason and scramble your mind.

Here’s the trick I would use - and it’s simple to do.
I’d define a procedure - we’ll name the thing Q -
that would take any program and call P (of course!)
to tell if it looped, by reading the source;

And if so, Q would simply print “Loop!” and then stop;
but if no, Q would go right back to the top,
and start off again, looping endlessly back,
til the universe dies and is frozen and black.

And this program called Q wouldn’t stay on the shelf;
I would run it, and (fiendishly) feed it itself.
What behaviour results when I do this with Q?
When it reads its own source, just what will it do?

If P warns of loops, Q will print “Loop!” and quit;
yet P is supposed to speak truly of it.
So if Q’s going to quit, then P should say, “Fine!” -
which will make Q go back to its very first line!

No matter what P would have done, Q will scoop it:
Q uses P’s output to make P look stupid.
If P gets things right then it lies in its tooth;
and if it speaks falsely, it’s telling the truth!

I’ve created a paradox, neat as can be -
and simply by using your putative P.
When you assumed P you stepped into a snare;
Your assumptions have led you right into my lair.

So, how to escape from this logical mess?
I don’t have to tell you; I’m sure you can guess.
By reductio, there cannot possibly be
a procedure that acts like the mythical P.

You can never discover mechanical means
for predicting the acts of computing machines.
It’s something that cannot be done. So we users
must find our own bugs; our computers are losers!

(more…)

Guaranteeing that you can take a hot shower is NP complete, at lest in one formalization the problem by Christina Matzke and Damien Challet in a recent paper.

Christina Matzke, Damien Challet, Taking a shower in Youth Hostels: risks and delights of heterogeneity, arXiv:0801.1573v1 , 10 January, 2008. … Tuning one’s shower in some hotels may turn into a challenging coordination game with imperfect information. The temperature sensitivity increases with the number of agents, making the problem possibly unlearnable. Because there is in practice a finite number of possible tap positions, identical agents are unlikely to reach even approximately their favorite water temperature. Heterogeneity allows some agents to reach much better temperatures, at the cost of higher risk.

Spotted on the physics arXiv blog.

xkcd has an IRC channel where its strange fans talk about even stranger things, some of the anyway. xkcd creator Randall Munroe discusses a common problem with IRC channels in a recent blog post ROBOT9000 and #xkcd-signal: Attacking Noise in Chat.

“When social communities grow past a certain point (Dunbar’s Number?), they start to suck. Be they sororities or IRC channels, there’s a point where they get big enough that nobody knows everybody anymore. The community becomes overwhelmed with noise from various small cliques and floods of obnoxious people and the signal-to-noise ratio eventually drops to near-zero — no signal, just noise. This has happened to every channel I’ve been on that started small and slowly got big.”

After laying out the standard approaches to controlling the problem (entry requirements, moderation, side channels) Randall describes a novel approach that fits oh so well with the xkcd community.

“And then I had an idea — what if you were only allowed to say sentences that had never been said before, ever? A bot with access to the full channel logs could kick you out when you repeated something that had already been said. There would be no “all your base are belong to us”, no “lol”, no “asl”, no “there are no girls on the internet”. No “I know rite”, no “hi everyone”, no “morning sucks.” Just thoughtful, full sentences.”

The idea’s implementation as a Perl bot sounds workable — when you violate the xkcd protocol by uttering a non-novel statement you are muted to prevent chatting for two second and the mute time quadruples for every subsequent violation. The bot forgives you after a while — your mute-time decays by half every six hours or so. You can read more about it on the xkcd blog or experience its tight rein on #xkcd-signal at irc.xkcd.com.

Not surprisingly, the channel is currently overwhelmed by chatters testing the bot to learn the finer points of its rules and how to subvert them. Hopefully, this is just a transient phenomenon and the robotic enforcement of novelty will evolve into something truly useful — a kindler, gentler moderator who can keep discussion from degenerating. But some serious tinkering will be required — common and repetitious utterances (”good morning”) are part of our social protocol, so this needs to be allowed to some degree.

Hatebook is an “anti-social utility that connects you with the people YOU HATE.” Unique among social networking sites, you can use it to “upload blackmail material or publish lies, get the latest gossip from your enemies and friends • post photos and videos on your hate profile • tag your friends • … get hate points from disturbing people who live, study, or work around you …”. Hatebook has nothing but disdain for its own users, which are it addresses as “suckers”.

It’s a fairly intricate parody of Facebook and other social networking sites, but one you are likely to find amusing, if at all, for only a few hours. Unless, of course, you are seriously angry and hateful, in which case you might find Hatebook to annoying to tolerate. (link)

Here’s a practical, scientific result.

A Game Theoretic Approach to the Toilet Seat Problem, Richard Harter, Science Creative Quarterly, number four, January 2006.

The toilet seat problem has been the subject of much controversey. In this paper we consider a simplified model of the toilet seat problem. We shall show that for this model there is an inherent conflict of interest which can be resolved by a equity solution.

Consider a bathroom with one omnipurpose toilet (also known as a WC) which is used for two toilet operations which we shall designate as #1 and #2. The toilet has an attachment which we shall refer to as the seat (but see remark 1 below) which may be in either of two positions which we shall designate as up and down.
…

Anand mentioned the (alleged) British spy rock as a good example of an advance that pervasive computing technology has wrought.

Russia’s state security service has accused British diplomats of spying in Moscow using electronic rocks. It’s an obvious hack, when you think about it — a bluetooth enabled PDA in a hollowed out rock could be used to drop off or pickup heavily encrypted documents from spys as they stroll by. The only problem would be power. Such a bluetooth rock would be much better than Alger Hiss’s pumpkin patch.

In an infamous spy case from the early days of the cold war, US State Department official Alger Hiss was accused (by a young Richard Nixon!) of passing documents via rolls of microfilm secreted in a hollowed-out pumpkin on his Maryland farm. But, technology marches on, with wireless rocks replacing pumpkins.

The March of Progress
1948	2006
In 1948 Alger Hiss was accused of transferring secrets using microfilm in a hollowed out pumpkin.	In 2006 the British were accused of transferring secrets using a wireless enabled PDA in a hollowed out rock.
cost: low encryption: no durability: low models: Jack-o’-lantern, squash vulnerable to: rodents, fungus, kids pluses: organic, biodegradable negatives: decay, rot	cost: medium encryption: yes durability: high models: igneous, sedimentary vulnerable to: bluejacking, spyware pluses: tetris, plays mp3s negatives: heavy