Gödel's Sentence Is An Adversarial Example But Unsolvable
This addresses a foundational problem in machine learning by suggesting adversarial examples may be inherently unsolvable, which is significant for researchers and practitioners in AI security.
The paper tackles the fundamental questions of why adversarial examples exist and whether they are unsolvable, showing that Gödel's sentence is an adversarial example that cannot be eliminated by data or algorithm improvements, and proving the incomputability of adversarial examples.
In recent years, different types of adversarial examples from different fields have emerged endlessly, including purely natural ones without perturbations. A variety of defenses are proposed and then broken quickly. Two fundamental questions need to be asked: What's the reason for the existence of adversarial examples and are adversarial examples unsolvable? In this paper, we will show the reason for the existence of adversarial examples is there are non-isomorphic natural explanations that can all explain data set. Specifically, for two natural explanations of being true and provable, Gödel's sentence is an adversarial example but ineliminable. It can't be solved by the re-accumulation of data set or the re-improvement of learning algorithm. Finally, from the perspective of computability, we will prove the incomputability for adversarial examples, which are unrecognizable.