Mathematicians Have Developed a Computing Problem That AI Can Never Solve | Tech - ScienceAlert

Not everything is knowable. In a world where it seems like artificial intelligence and machine learning can figure out just about anything, that might seem like heresy – but it's true, argues Peter Dockrill, Senior Writer at Science Alert.

Photo: tostphoto/iStock

At least, that's the case according to a new international study by a team of mathematicians and AI researchers, who discovered that despite the seemingly boundless potential of machine learning, even the cleverest algorithms are nonetheless bound by the constraints of mathematics.

"The advantages of mathematics, however, sometimes come with a cost… in a nutshell… not everything is provable," the researchers, led by first author and computer scientist Shai Ben-David from the University of Waterloo, write in their paper.

"Here we show that machine learning shares this fate."

Awareness of these mathematical limitations is often tied to the famous Austrian mathematician Kurt Gödel, who developed in the 1930s what are known as the incompleteness theorems – two propositions suggesting that not all mathematical questions can actually be solved.

Now, Ben-David's new research indicates that machine learning is limited by the same unresolvability.

In this argument, a machine's ability to actually learn – called learnability – can be constrained by mathematics that is unprovable. In other words, it's basically giving an AI an undecidable problem, something that's impossible for an algorithm to solve with a true-or-false response.

"For us, it was a surprise," senior researcher and mathematician Amir Yehudayoff, from the Technion-Israel Institute of Technology, explained to Nature...

According to the researchers, in this kind of case, the mathematical problem to be solved bears similarities to a machine learning framework known as probably approximately correct learning (aka PAC learning), but it's also similar to a mathematical paradox called the continuum hypothesis, another field of investigation for Gödel...

The findings are reported in Nature Machine Intelligence.
Read more... 

Source: ScienceAlert