# A Computability Perspective on (Verified) Machine Learning

arXiv: https://arxiv.org/abs/2102.06585 · HTML: https://mlsanity.com/paper/2102.06585/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 37 references that are in the map.
- First posted on arXiv 12 Feb 2021.

## Builds on (most cited first, 16 of 16)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [Reachability Analysis of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1805.02242/) (2018)
- [Feature-Guided Black-Box Safety Testing of Deep Neural Networks](https://mlsanity.com/paper/1710.07859/) (2017)
- [Geometry-Based Data Generation](https://mlsanity.com/paper/1802.04927/) (2018)
- [Weihrauch Complexity in Computable Analysis](https://mlsanity.com/paper/1707.03202/) (2017)
- [Point degree spectra of represented spaces](https://mlsanity.com/paper/1405.6866/) (2014)
- [Noetherian Quasi-Polish Spaces](https://mlsanity.com/paper/1607.07291/) (2016)
- [Overt choice](https://mlsanity.com/paper/1902.05926/) (2019)
- [Effective local compactness and the hyperspace of located sets](https://mlsanity.com/paper/1903.05490/) (2019)
- [Decision problems for linear recurrences involving arbitrary real numbers](https://mlsanity.com/paper/2008.00583/) (2020)
- [Adaptive Neighbourhoods for the Discovery of Adversarial Examples](https://mlsanity.com/paper/2101.09108/) (2021)

## Built on by (most cited first, 3 of 3)

- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)
- [On computable learning of continuous features](https://mlsanity.com/paper/2111.14630/) (2021)
- [Uniform Computability of PAC Learning](https://mlsanity.com/paper/2601.18663/) (2026)

## Abstract (arXiv)

There is a strong consensus that combining the versatility of machine learning with the assurances given by formal verification is highly desirable. It is much less clear what verified machine learning should mean exactly. We consider this question from the (unexpected?) perspective of computable analysis. This allows us to define the computational tasks underlying verified ML in a model-agnostic way, and show that they are in principle computable.