Подход, основанный на изучении "идентификации в пределе", в основном посвящен достигаемой в конечном итоге сходимости, а исследования колмогоровской сложности, или алгоритмической сложности, проведенные независимо Соломоновым [1445] и Колмогоровым [828], представляют собой попытку дать формальное определение понятия простоты, используемого в принципе бритвы Оккама. Чтобы исключить проблему, связанную с тем, что простота зависит от способа представления информации, было предложено измерять простоту как длину кратчайшей программы для универсальной машины Тьюринга, которая правильно воспроизводит наблюдаемые данные. Хотя существует много возможных универсальных машин Тьюринга и поэтому много возможных "кратчайших" программ, было обнаружено, что эти программы отличаются по длине не больше чем на некоторую константу, независимую от объема данных. Это — великолепное открытие, которое по сути показывает, что любое искажение в первоначальном представлении данных в конечном итоге должно быть преодолено с помощью самих же данных. Его широкому применению препятствует лишь то, что задача вычисления длины кратчайшей программы является неразрешимой. Однако вместо точного значения длины могут применяться такие приближенные критерии, как минимальная длина описания, или MDL (Minimum Description Length) [1291], которые позволяют добиться на практике превосходных результатов. Наилучшим источником сведений по проблеме колмогоровской сложности является книга Ли и Витаньи [927].

Теория вычислительного обучения (т.е. теория РАС-обучения) была выдвинута Лесли Валиантом [1528]. В работе Валианта подчеркивается важность вычислительной и выборочной сложности. Совместно с Майклом Кернсом [783] Валиант показал, что задача РАС-обучения некоторых классов концепций является трудноразрешимой, даже если в примерах присутствует достаточный объем информации. Некоторые положительные результаты были получены для таких классов, как списки решений [1293].