Уравнения в словах в свободном моноиде.

Учебный год

Г.И. Сыркин читает спецкурс

«Введение в алгоритмическую алгебру»

по четвергам, с 16 час. 45 мин. до 18 час. 30 мин.

в аудитории 463 наВМК

Первая лекция состоится 24 сентября.

Примерная программа на 1-й семестр 2015-2016 учебного года

Частично рекурсивные функции как вариант формализации понятия алгоритма (вычислимой функции).

1.1. Понятие n-местной частичной функции (на множестве натуральных чисел и со значениями во множестве натуральных чисел). Несчётность множества всех одноместных всюду определённых функций.

n-местный (частично рекурсивный) операторный терм как изображение (или «программа»), представляющая n-местную частично рекурсивную функций. Индуктивное определение n-местных операторных термов. Исходные (основные) операторные термы, представляющие одноместную нулевую функцию, (одноместную) функцию следования, проектирующие многоместные функции.

Операторы композиции, примитивной рекурсии. Оператор минимизации.

n-местные примитивно рекурсивные функции как n-местные примитивно рекурсивные операторные термы. n-местные частично рекурсивные функции как n-местные частично рекурсивные операторные термы.

Понятие n-местной общерекурсивной функции. Представление примитивно рекурсивными операторными термами операций сложения, умножения, возведения в степень, взятия факториала. Теорема о невозможности универсальной (n+1)-местной примитивно-рекурсивной функции для класса всех n-местных примитивно-рекурсивных функций.

Теорема Р.Робинсон о порождаемости класса всех одноместных примитивно-рекурсивных функций из функции следования s и функции взятия квадратичного остатка q с помощью операций сложения, композиции и итерирования функций (без доказательства).

Быстрорастущие общерекурсивные функции, диагональная функция Аккермана как пример общерекурсивной функции, не являющейся примитивно-рекурсивной функцией, теорема Аккермана (с доказательством).

1.2. Протокол успешно завершённого применения n-местной частично-рекурсивной функции к входному n-членному набору натуральных чисел. Нумерация (кодирование) конструктивных объектов словами алфавита, натуральными числами (гёделева нумерация). Нумерация (кодирование) натуральными числами протоколов (успешно завершённых) вычислений. Теорема о существовании универсальной (n+1)-местной частично-рекурсивной функции для класса всех n-местных частично-рекурсивных функций (эскиз доказательства). Теорема о невозможности общерекурсивного продолжения универсальной (n+1)-местной частично-рекурсивной функции для класса всех n-местных частично-рекурсивных функций.

Теоремы о невозможности алгоритмов, решающих некоторые алгоритмические проблемы (проблемы распознавания самоприменимости алгоритмов, проблемы распознавания всюду применимости алгоритмов и т.д.). Теорема Райса об алгоритмической неразрешимости (нераспознаваемости) нетривиальных инвариантных свойств алгоритмов (частично-рекурсивных функций) (без доказательства). Примеры применения Теоремы Райса к доказательству теорем о невозможности алгоритмов, решающих некоторые алгоритмические проблемы.

Метод устранения кванторов. Алгоритмическая разрешимость теорий некоторых классов алгебраических систем.

2.1. Арифметика Пресбургера (арифметика сложения целых чисел с отношением порядка). Арифметика сложения натуральных чисел. Взаимная интерпретируемость арифметики сложения целых чисел с отношением порядка и арифметики сложения натуральных чисел. Расширение исходной сигнатуры арифметики Пресбургера с помощью счётного множества символов двуместных отношений сравнения по модулям. Свойства (=одноместные предикаты), выразимые в исходной сигнатуре.

Невыразимость одноместного предиката «быть чётным» в исходной сигнатуре. Теорема Пресбургера об устранимости кванторов в арифметике Пресбургера в расширенной сигнатуре и разрешимости арифметика Пресбургера (теории сложения целых чисел с отношением порядка). Теорема Пресбургера о разрешимости элементарной теории сложения натуральных чисел. [Нижняя оценка (двойная экспонента) сложности разрешающего алгоритма*]. Примеры применения теоремы Пресбургера (в частности, алгоритм решения задачи целочисленного линейного программирования).

2.2. Теорема Тарского об устранимости кванторов в элементарной теории поля действительных чисел. Примеры применения теоремы Тарского: 1) Разрешающий алгоритм для элементарной теории поля действительных чисел. 2) Алгоритм, решающий проблемы аналитической геометрии n-мерных евклидовых пространств (n = 1, 2, 3,…), формализуемые в элементарной теории поля действительных чисел. 3) Алгоритм, решающий задачи с параметрами в элементарной математике, формализуемые в теории поля действительных чисел. 4) Алгоритм, решающий задачи оптимизации с «целевым» функционалом и «ресурсными» ограничениями, выразимыми в теории поля действительных чисел.

2.3. Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования и с кванторами второго порядка по всевозможным подмножествам (без доказательства).

Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования и с кванторами второго порядка по всевозможным конечным подмножествам (без доказательства).

Интерпретация элементарной теории (теории первого порядка) сложения натуральных чисел в слабой монадической теории второго порядка натуральных чисел с одной функцией следования s и с кванторами второго порядка по всевозможным конечным подмножествам. Вывод разрешимости элементарной теории сложения натуральных чисел.

Уравнения в словах в свободном моноиде.

Результат Г. С. Маканина о существовании алгоритма, распознающего разрешимость систем уравнений в словах в свободном моноиде. (без доказательства). Теорема Хмелевского о решениях бескоэффициентного уравнения с двумя неизвестными (с доказательством). Теорема Нильсена о кодировании слов двухбуквенного алфавита унимодулярными матрицами второго порядка с неотрицательными целыми элементами (с доказательством). Сведение систем уравнений в словах в двухбуквенном алфавите к соответствующей системе алгебраических уравнений в целых числах с целыми коэффициентами (с доказательством).

Обзор некоторых результатов о невозможности алгоритмов в алгебре (без доказательств).

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

Примечание.Весь спецкурс может быть сдан как годовой спецкурс, либо каждая из двух его частей может быть сдана независимо друг от друга как полугодовой спецкурс.

В программу спецкурса могут быть внесены изменения с учётом уровня подготовки и интересов слушателей.

Нужные для понимания спецкурса сведения по математической логике и алгебре будут кратко напоминаться по ходу лекций.

Доказательства некоторых лемм, теорем, а также изучение дополнительного материала могут быть предложены слушателям в качестве самостоятельной домашней работы с последующим обсуждением на спецкурсе или вне рамок спецкурса.

Информация о данном спецкурсе размещена на сайтах кафедры МаТИС:

http://www.intsys.msu.ru/, http://www.intsys.msu.ru/study/courses/algalg.htm

Поиск по сайту: