Еще один подход состоит в применении наибольшего возможного пространства гипотез. Например, почему бы не использовать в качестве Н класс всех машин Тьюринга? В конечном итоге любая вычислимая функция может быть представлена с помощью некоторой машины Тьюринга, и это — наилучший способ представления, который только может применяться. Но при реализации этой идеи возникает проблема, связанная с тем, что в ней не учитывается вычислительная сложность обучения. Необходимо найти компромисс между выразительностью пространства гипотез и сложностью поиска простой, совместимой гипотезы в этом пространстве. Например, подгонка к данным прямых линий осуществляется очень просто; подбор полиномов высокой степени становится сложнее, а создание соответствующих машин Тьюринга действительно представляет собой очень сложную задачу, поскольку неразрешима в общем виде даже проблема определения того, является ли конкретная машина Тьюринга совместимой с данными. Второй причиной, по которой следует предпочесть простые пространства гипотез, является то, что результирующие гипотезы могут оказаться более простыми в использовании, т.е. вычисление h(x), если h — линейная функция, будет осуществляться быстрее, чем при использовании программы, моделирующей произвольную машину Тьюринга.

По этим причинам основной объем исследований в области обучения был сосредоточен на относительно простых способах представления. В данной главе в основном рассматриваются пропозициональная логика и связанные с ней языки. В главе 19 рассматриваются теории обучения в логике первого порядка. Ниже будет показано, что компромисс между выразительностью и сложностью найти не так просто, как кажется на первый взгляд, поскольку, как было описано в главе 8, выразительный язык позволяет создать простую теорию, согласующуюся с данными, а ограничение выразительности языка приводит к тому, что любая согласованная теория должна стать очень сложной. Например, правила шахмат могут быть записаны в логике первого порядка на одной или двух страницах, но потребуют тысячи страниц при их формулировке в пропозициональной логике. Кроме того, в подобных случаях при использовании более выразительного языка намного ускоряется обучение.