Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

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

Учебный год

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

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

по четвергам, с 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