АЛГОРИТМИЧЕСКОЕ ОБУЧЕНИЕ ПОДПРОСТРАНСТВ В ВЫЧИСЛИМЫХ ВЕКТОРНЫХ ПРОСТРАНСТВАХ

Аннотация

Алгоритмическое обучение алгебраических структур связывает теорию вычислимости с искусственным интеллектом. Классический индуктивный вывод в основном имеет дело с формальными языками и рекурсивными функциями. В отличие от этого, анализ векторных пространств позволяет исследовать теоретические пределы автоматизированных научных открытий. Данное исследование изучает алгоритмическую обучаемость семейств подпространств в вычислимых векторных пространствах над вычислимым полем. Мы сосредотачиваемся на фундаментальном семействе всех конечномерных подпространств и выясняем, является ли обучаемость инвариантом изоморфизма. Объединяя теорию конструктивных моделей с парадигмой Голда об идентификации в пределе, наши результаты выявляют точные рекурсивно-теоретические барьеры для обучения алгебраическим инвариантам. Мы используем классическую модель объяснительного обучения в пределе по позитивным данным (Ex-обучение), где в качестве обучающихся агентов выступают машины Тьюринга. При меняя канонические нумерации конечных множеств и конструкции эффективных фактор пространств, мы устанавливаем две фундаментальные теоремы. Наш первый результат показывает, что если вычислимое векторное пространство имеет разрешимое отношение линейной зависимости, то семейство всех его конечномерных подпространств является Ex-обучаемым. Во-вторых, мы строим вычислимое векторное пространство, в котором отношение линейной зависимости неразрешимо. Используя эффективный метод диагонализации с приоритетами, мы доказываем, что семейство конечномерных подпространств в этом пространстве не является Ex-обучаемым. Эти результаты доказывают, что алгоритмическая обучаемость не является инвариантом изоморфизма абстрактной алгебраической структуры. Напротив, она строго определяется алгоритмической сложностью (тьюринговой степенью) предиката линейной зависимости. Данный вывод предоставляет теоретическую основу для систем автоматического доказательства теорем и нейросимволического искусственного интеллекта.