Category: Uncategorized

Well, happy belated birthday. November 18th was the 71st anniversary of the publication of Turing’s seminal paper, “On Computable Numbers with an Application to the Entscheidungsproblem“.

As described on Wikipedia:

In mathematics, the Entscheidungsproblem (German for ‘decision problem‘) is a challenge posed by David Hilbert in 1928. The Entscheidungsproblem asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either “True” or “False” according to whether the statement is true or false. The algorithm need not justify its answer, nor provide a proof, so long as it is always correct. Such an algorithm would be able to decide, for example, whether statements such as Goldbach’s conjecture or the Riemann hypothesis are true, even though no proof or disproof of these statements is known. The Entscheidungsproblem has often been identified in particular with the decision problem for first-order logic (that is, the problem of algorithmically determining whether a first-order statement is universally valid).

In 1936 and 1937, Alonzo Church and Alan Turing, respectively, published independent papers showing that it is impossible to decide algorithmically whether statements in arithmetic are true or false, and thus a general solution to the Entscheidungsproblem is impossible. This result is now known as Church’s Theorem or the Church-Turing Theorem (not to be confused with the Church–Turing thesis).

Shortly after finishing my undergraduate studies at MIT, I had the privilege of attending a brunch with Gian-Carlo Rota and some of his colleagues who represented a who’s who of local combinatorists. We got to talking about the halting problem, and someone asked me if it wasn’t just a contrived example of dubious relevance to computer science as a whole. Even then, I felt strongly that the halting problem, or it’s equivalent formulation in terms of Gödel’s incompleteness theorems, was at the heart of theoretical computer science, along with the still unsolved P vs. NP question.

So, happy birthday, dear Turing machine. You’re aged marvelously.

(Via The Register)

Somehow the story of whether Microsoft should acquire Yahoo just can’t stay out of the news. But what’s more interesting is that Microsoft seems to be poaching key talent from Yahoo Search. I’m still not writing Yahoo off, but they seem to be increasingly playing the part of a pawn in the struggle between Google and Microsoft to own web search.

Just read the news that the print edition of PC Magazine is shutting down. Here’s a touching requiem by Michael Miller, their long-time editor-in-chief. Interesting times for old media.

Fresh from Kas Thomas at CMS Watch: “RSS is more than aggregation — it’s the new personalization“. 

Here’s a teaser:

Bottom line? Feed-based delivery of content isn’t just about aggregation; it’s about empowering users — giving them the power to choose how they want to consume content. 

Better yet, he shows an example of building his own version of the ArnoldIT “Overflight” aggregation service as an RSS feed using Yahoo Pipes. This is well beyond the call of duty for an analyst–check it out!

Apparently the new voice-recognition tool for the iPhone has problems understanding British accents, leading to some amusing mishaps. Have no fear, the article is safe for work.

Nice post from Gil Yehuda at Forrester entitled “Enterprise Mashups Need Complexity to Create Value“.

Here’s an excerpt:

So, if you combine two mashups and couple of data feeds, you can create transformative value from readily available information. I had faith this could be created, but now that I see signals that others are implementing solutions like this. I have renewed faith in the relevance of mashups to enterprise computing. It’s just more complex than splashing a data set onto a map. That’s OK, enterprises are used to leveraging complexity to create value. And mashups can be the building blocks to enable their success.

No shocking insights there, but it’s an articulate and sober explanation of the value that enterprise mashups can create.

I’d just hit “publish” on my last post about the challenges of faceted search for the web when I saw this post from Jeff about Yahoo announced an extension to their public BOSS API that provides “key terms” for search results.

Jeff quotes this excerpt from their description:

Key Terms is derived from a Yahoo! Search capability we refer to internally as “Prisma.”… Key Terms is an ordered terminological representation of what a document is about. The ordering of terms is based on each term’s frequency and its positional and contextual heuristics…Each result contains up to 20 terms describing the document.

Yes, I know, key terms aren’t a faceted classification. And I don’t know what quality or consistency this feature provides. Still, it’s a step towards addressing the first and most serious challenge raised in the Microsoft researchers’ position paper. And it’s nice to see news about Yahoo beyond the saturation coverage of Jerry Yang stepping down.

Surprisingly good reporting in the mainstream media (specifically, the Washington Post) about how shutting down McColo reduced worldwide spam volume by 65%.

Here’s a choice quote about why spammers prefer to host their servers in the United States:

What’s more, dependability and server uptime are important in cutthroat businesses for which an outage of a few hours can staunch the flow of spam and cost thousands of dollars. 

Hey, business is business, even for evil spammers.

OK, this is an oldie but goodie from xkcd, but I saw it in a recent presentation and couldn’t resist sharing.

Of course, you’d never know that from the sensationlist press.

Thanks to Daniel Lemire for point to this recent paper by Peter Turney on “A Uniform Approach to Analogies, Synonyms, Antonyms, and Associations“.

Daniel Lemire consider this paper an example of the “more data beats better algorithms” principle most famously espoused by Google Director of Research Peter Norvig.

My take is a bit different. One message I heard repeatedly at the recent NSF Symposium on Semantic Knowledge Discovery, Organization and Use is that semantic researchers need to reduce their problem space to make progress. Peter is doing exactly that in his own work by taking what are perceived as distinct problems and generalizing them in order to treat them uniformly. Perhaps the broader community could profit from his approach and, um, learn by analogy.