The Simple Problem Machines Can’t Solve

“I do apologize for not being able to satisfy a lot of people’s expectations. I kind of felt powerless,” [1], said GO grandmaster Lee Sedol after a surprising 1-4 loss to the artificial intelligence AlphaGO recently.

Machines had conquered most of the games mankind has created, including chess, Scrabble, and even Jeopardy!.  The ancient game GO, exponentially more complex than chess, was once considered to be one of the ultimate tests of machines’ capabilities. Yet with Lee’s loss, the game has been conquered. Given the rapid advances in artificial intelligence, one cannot help but wonder “Is there any limit to what a machine can do?”

While machines have become smart enough to defeat humans in sophisticated games, humans have cleverly devised a problem that machines definitely cannot solve. Impressively, the problem was constructed more than 80 years ago, even before the birth of digital computers. The star of humanity who came up with this construction was mathematician Kurt Godel. Later, Alan Turing, the father of computer science, used Godel’s techniques to prove an analogous theorem in the context of computer science. In its simplest form, this theorem states that there exist problems that a machine will never be able to conquer. Continue reading

Why computer scientists and linguists don’t always see eye-to-eye

Linguists have many theories about how language works. How much should computer scientists who work on language care?

Linguists have many theories about how language works. But how much should the computer scientists who work with language care? (CC image courtesy of Flickr/surrealmuse)

“You’ve just explained my entire life to me.” This was the last thing I was expecting to hear from Lori, my graduate advisor, in the midst of a discussion of my career plans. I gave a stiff smile and shifted uncomfortably in my chair. “What you just said,” she continued, “that’s why I’m here, not in a linguistics department. In a linguistics department in the 80’s, I might have felt like a hypocrite.”

What I’d said hadn’t been a deliberate attempt to enlighten a researcher 30 years my senior. I’d simply mentioned my preference for application-oriented research groups, because I care more about producing useful insights than true theories. Apparently, though, the distinction between usefulness and truth struck a chord with Lori: in the field she and I work in, what’s useful isn’t always true, and what’s true is often not useful. Lori, a linguist in a school of computer science, has found her career path to be largely determined by that distinction.

Continue reading

The Cosmos’ Attack on Computers

In 1984, IBM encountered a mystery: computers in Denver were making ten times more unexplained mistakes than the national average. The operators of the computers kept reporting memory errors, but whenever they sent a memory unit back to IBM, the company could find nothing physically wrong. Why wouldn’t computers work properly in Denver?

For several years, the operators had to work around the fact that their computers would occasionally just forget things. It was almost like the computers were high – which, it turned out, was precisely the problem. At 5,280 feet, computers in Denver are much more susceptible to an unlikely culprit: cosmic rays. Continue reading