Уважаемые коллеги!

16 ноября (пятница) в 16:00 часов в 610 аудитории состоится доклад Пузаренко Вадима Григорьевича (ведущий научный сотрудник ИМ СО РАН, профессор Новосибирского университета, Новосибирск) в рамках семинара кафедры алгебры и математической логики.

Тема доклада: " Вычислимая структура с нестандартной вычислимостью"

Аннотация: Одним из обобщений теории конструктивных моделей является, с одной стороны, нахождение сравнительных характеристик пар структур относительно друг друга (к примеру, структура A сложнее структуры B, если структура A позволяет найти эффективные представления всех структур, имеющих эффективные задания структуры относительно B); а с другой стороны, для фиксированной структуры B нахождение класса структур, имеющих эффективное представление относительно структуры B. Академик Ю.Л. Ершов предложил рассматривать в качестве структур, на которых заданы эффективные представления, допустимые множества. Этот класс структур является достаточно богатым и, к тому же, содержит структуру N, близкую к натуральным числам. Структура N является самой бедной в рассматриваемой иерархии с точки зрения класса эффективно представленных в ней структур и содержит в точности все вычислимые структуры. В последнее время не только в России, но и за рубежом проводятся активные исследования производной структуры, в которой проводится сравнительный анализ допустимых структур с точки зрения объемности эффективных представлений. Основным результатом предложенной работы является наличие допустимой структуры H, имеющей эффективное задание в N (а именно, вычислимой как структуры), но имеющей более высокую сложность вычислимости, нежели N (что равносильно тому, что имеется невычислимая алгебра, имеющая эффективное представление в H). Для доказательства развивается теория представлений гипердопустимых множеств, в которых алгебра, над которой она строится, является элементом. Кроме того, для построения подходящей допустимой структуры понадобились неразрешимые структуры теории графов.

Приглашаем Вас принять участие.