This post is making the rounds of the internet:

Shirt without Stripes

Search results for Google, Amazon and Bing, when searching for “shirt without stripes”.

AI/ML
Amazon: https://aws.amazon.com/machine-learning/
Microsoft: https://www.microsoft.com/en-us/ai
Google: https://ai.google/

Assistants
Amazon: https://developer.amazon.com/en-US/alexa
Microsoft: https://www.microsoft.com/en-us/cortana
Google: https://assistant.google.com/

The author shows that the top three search AI companies: Google, Microsoft and Amazon, all gave absurd results to the simple query, “shirt without stripes,” namely a bunch of shirts with stripes.

So, why are the most commercially successful AI companies so bad at understanding a simple statement that all humans can easily understand?

Do they need better algorithms and better training data? More elbow grease applied to the problem? Why is it so hard to recognize that “X without Y” means to show Xs without Ys?

The problem is that human language is at least as complex as computer language. And computers cannot understand their own language. This is known as the halting problem:

The problem of determining in advance whether a particular program or algorithm will terminate or run forever. The halting problem is the canonical example of a provably unsolvable problem. Obviously any attempt to answer the question by actually executing the algorithm or simulating each step of its execution will only give an answer if the algorithm under consideration does terminate, otherwise the algorithm attempting to answer the question will itself run forever.

– The Free On-line Dictionary of Computing. S.v. “halting problem.” Retrieved April 21 2020 from https://encyclopedia2.thefreedictionary.com/halting+problem

So the halting problem is that it is impossible for a computer to determine whether a program will halt or not. Alan Turing proved that in 1936.

At first, the problem might not seem like much of an issue but it turns out that many important and interesting problems for computers fundamentally reduce to the halting problem. Understanding human language is one of these problems.

But, how do we know human language reduces to the halting problem? The proof is very simple.

We can use human language to describe any possible computer language. Since computers cannot understand computer languages due to the halting problem, they consequently cannot understand a language that can describe a computer language. Their lack of ability to understand is also due to the halting problem.

Therefore, computers cannot understand human languages, and that is why they cannot understand even simple phrases like “shirts without stripes.”

Further thoughts from Eric Holloway on the halting problem:

Human intelligence as a halting oracle. Jonathan Bartlett proposes to model the human mind as a halting oracle.

and

Could one single machine invent everything? A tale.