Different levels of learnability

In this work we study some features of learning theory, using tools from descriptive set theory. After introducing the fundamental objects about learnability and basilar results on reductions between equivalence relations, we give a descriptive set-theoretical characterization of the learnability of a family of structures through the equivalence relation of eventual agreement on the Cantor space. Then, we study different levels of learnability considering other (more complex) equivalence relations on the same space, showing that families of structures that are not learnable in the classical way become learnable at a different learnability level. In the final chapter, we investigate the number of mind changes in a learning process, and we characterize the families that are learnable with a fixed number of mind changes.

In questo lavoro studiamo alcune caratteristiche della learning theory, usando strumenti di teoria descrittiva degli insiemi. Dopo aver introdotto oggetti fondamentali nel campo dell'apprendibilità e risultati di base sulla riduzione tra relazioni di equivalenza, diamo una caratterizzazione in termini di teoria descrittiva degli insiemi dell'apprendibilità di una famiglia di strutture tramite una relazione di equivalenza sullo spazio di Cantor. Quindi studiamo diversi livelli di apprendibilità considerando altre (più complesse) relazioni di equivalenza sullo stesso spazio, mostrando che famiglie di strutture che non sono apprendibili nella maniera classica diventano apprendibili ad un diverso livello di apprendibilità. Nel capitolo finale, analizziamo il numero di cambi di ipotesi in un processo di apprendimento e caratterizziamo le famiglie che sono apprendibili con un numero fissato di cambi di ipotesi.