On the Uniform Learnability of Approximations to Non-recursive Functions

摘要

Blum and Blum (1975) showed that a class B of suitable recursive approximations to the halting problem is reliably EX-learnable. These investigations are carried on by showing that B is neither in NUM nor robustly EX-learnable. Since the definition of the class B is quite natural and does not contain any self-referential coding, B serves as an example that the notion of robustness for learning is quite more restrictive than intended.