Researchers from the University of Copenhagen have become the first in the world to mathematically prove that, beyond simple problems, it is impossible to develop algorithms for AI that will always be stable.
ChatGPT and similar machine learning-based technologies are on the rise. However, even the most advanced algorithms face limitations. Researchers from the University of Copenhagen have made a groundbreaking discovery, mathematically demonstrating that, beyond basic problems, it’s impossible to develop AI algorithms that are always stable. This research could pave the way for improved testing protocols for algorithms, highlighting the inherent differences between machine processing and human intelligence.
The scientific article describing the result has been approved for publication at one of the leading international conferences on theoretical computer science.
Machines interpret medical scanning images more accurately than doctors, translate foreign languages, and may soon be able to drive cars more safely than humans. However, even the best algorithms do have weaknesses. A research team at the Department of Computer Science, University of Copenhagen, tries to reveal them.
Take an automated vehicle reading a road sign as an example. If someone has placed a sticker on the sign, this will not distract a human driver. But a machine may easily be put off because the sign is now different from the ones it was trained on.
“We would like algorithms to be stable in the sense, that if the input is changed slightly the output will remain almost the same. Real life involves all kinds of noise which humans are used to ignore, while machines can get confused,” says Professor Amir Yehudayoff, heading the group.
A language for discussing weaknesses
As the first in the world, the group together with researchers from other countries has proven mathematically that apart from simple problems it is not possible to create algorithms for Machine Learning that will always be stable. The scientific article describing the result was approved for publication at one of the leading international conferences on theoretical computer science, Foundations of Computer Science (FOCS).
“I would like to note that we have not worked directly on automated car applications. Still, this seems like a problem too complex for algorithms to always be stable,” says Amir Yehudayoff, adding that this does not necessarily imply major consequences in relation to the development of automated cars:
“If the algorithm only errs under a few very rare circumstances this may well be acceptable. But if it does so under a large collection of circumstances, it is bad news.”
The scientific article cannot be applied by the industry to identify bugs in its algorithms. This wasn’t the intention, the professor explains:
“We are developing a language for discussing the weaknesses in Machine Learning algorithms. This may lead to the development of guidelines that describe how algorithms should be tested. And in the long run, this may again lead to the development of better and more stable algorithms.”
From intuition to mathematics
A possible application could be for testing algorithms for the protection of digital privacy.
”Some companies might claim to have developed an absolutely secure solution for privacy protection. Firstly, our methodology might help to establish that the solution cannot be absolutely secure. Secondly, it will be able to pinpoint points of weakness,” says Amir Yehudayoff.
First and foremost, though, the scientific article contributes to theory. Especially the mathematical content is groundbreaking, he adds: ”We understand intuitively, that a stable algorithm should work almost as well as before when exposed to a small amount of input noise. Just like the road sign with a sticker on it. But as theoretical computer scientists, we need a firm definition. We must be able to describe the problem in the language of mathematics. Exactly how much noise must the algorithm be able to withstand, and how close to the original output should the output be if we are to accept the algorithm to be stable? This is what we have suggested an answer to.”
Important to keep limitations in mind
The scientific article has received large interest from colleagues in the theoretical computer science world, but not from the tech industry. Not yet at least.
”You should always expect some delay between a new theoretical development and interest from people working in applications,” says Amir Yehudayoff while adding smilingly: ”And some theoretical developments will remain unnoticed forever.”
However, he does not see that happening in this case: ”Machine Learning continues to progress rapidly, and it is important to remember that even solutions which are very successful in the real world still do have limitations. The machines may sometimes seem to be able to think but after all, they do not possess human intelligence. This is important to keep in mind.”
Reference: “Replicability and Stability in Learning” by Zachary Chase, Shay Moran and Amir Yehudayoff, 2023, Foundations of Computer Science (FOCS) conference.
DOI: 10.48550/arXiv.2304.03757

News
Repurposed drugs could calm the immune system’s response to nanomedicine
An international study led by researchers at the University of Colorado Anschutz Medical Campus has identified a promising strategy to enhance the safety of nanomedicines, advanced therapies often used in cancer and vaccine treatments, [...]
Nano-Enhanced Hydrogel Strategies for Cartilage Repair
A recent article in Engineering describes the development of a protein-based nanocomposite hydrogel designed to deliver two therapeutic agents—dexamethasone (Dex) and kartogenin (KGN)—to support cartilage repair. The hydrogel is engineered to modulate immune responses and promote [...]
New Cancer Drug Blocks Tumors Without Debilitating Side Effects
A new drug targets RAS-PI3Kα pathways without harmful side effects. It was developed using high-performance computing and AI. A new cancer drug candidate, developed through a collaboration between Lawrence Livermore National Laboratory (LLNL), BridgeBio Oncology [...]
Scientists Are Pretty Close to Replicating the First Thing That Ever Lived
For 400 million years, a leading hypothesis claims, Earth was an “RNA World,” meaning that life must’ve first replicated from RNA before the arrival of proteins and DNA. Unfortunately, scientists have failed to find [...]
Why ‘Peniaphobia’ Is Exploding Among Young People (And Why We Should Be Concerned)
An insidious illness is taking hold among a growing proportion of young people. Little known to the general public, peniaphobia—the fear of becoming poor—is gaining ground among teens and young adults. Discover the causes [...]
Team finds flawed data in recent study relevant to coronavirus antiviral development
The COVID pandemic illustrated how urgently we need antiviral medications capable of treating coronavirus infections. To aid this effort, researchers quickly homed in on part of SARS-CoV-2's molecular structure known as the NiRAN domain—an [...]
Drug-Coated Neural Implants Reduce Immune Rejection
Summary: A new study shows that coating neural prosthetic implants with the anti-inflammatory drug dexamethasone helps reduce the body’s immune response and scar tissue formation. This strategy enhances the long-term performance and stability of electrodes [...]
Scientists discover cancer-fighting bacteria that ‘soak up’ forever chemicals in the body
A family of healthy bacteria may help 'soak up' toxic forever chemicals in the body, warding off their cancerous effects. Forever chemicals, also known as PFAS (per- and polyfluoroalkyl substances), are toxic chemicals that [...]
Johns Hopkins Researchers Uncover a New Way To Kill Cancer Cells
A new study reveals that blocking ribosomal RNA production rewires cancer cell behavior and could help treat genetically unstable tumors. Researchers at the Johns Hopkins Kimmel Cancer Center and the Department of Radiation Oncology and Molecular [...]
AI matches doctors in mapping lung tumors for radiation therapy
In radiation therapy, precision can save lives. Oncologists must carefully map the size and location of a tumor before delivering high-dose radiation to destroy cancer cells while sparing healthy tissue. But this process, called [...]
Scientists Finally “See” Key Protein That Controls Inflammation
Researchers used advanced microscopy to uncover important protein structures. For the first time, two important protein structures in the human body are being visualized, thanks in part to cutting-edge technology at the University of [...]
AI tool detects 9 types of dementia from a single brain scan
Mayo Clinic researchers have developed a new artificial intelligence (AI) tool that helps clinicians identify brain activity patterns linked to nine types of dementia, including Alzheimer's disease, using a single, widely available scan—a transformative [...]
Is plastic packaging putting more than just food on your plate?
New research reveals that common food packaging and utensils can shed microscopic plastics into our food, prompting urgent calls for stricter testing and updated regulations to protect public health. Beyond microplastics: The analysis intentionally [...]
Aging Spreads Through the Bloodstream
Summary: New research reveals that aging isn’t just a local cellular process—it can spread throughout the body via the bloodstream. A redox-sensitive protein called ReHMGB1, secreted by senescent cells, was found to trigger aging features [...]
AI and nanomedicine find rare biomarkers for prostrate cancer and atherosclerosis
Imagine a stadium packed with 75,000 fans, all wearing green and white jerseys—except one person in a solid green shirt. Finding that person would be tough. That's how hard it is for scientists to [...]
Are Pesticides Breeding the Next Pandemic? Experts Warn of Fungal Superbugs
Fungicides used in agriculture have been linked to an increase in resistance to antifungal drugs in both humans and animals. Fungal infections are on the rise, and two UC Davis infectious disease experts, Dr. George Thompson [...]