name: Алгоритмы квазиэлиминации кванторов и вопросы выразимости в арифметиках с делимостью
keyword_list: Теории первого порядка Слабые арифметики Целочисленная делимость Взаимная простота Выразимость Алгоритмическая разрешимость Элиминация кванторов
abstract: Актуальность темы исследования.
  	Диссертация посвящена исследованию связи между двумя важными инструментами, применяемыми при изучении вопросов теоретической информатики: алгоритмами элиминации кванторов и теоремы о разрешимости экзистенциальной теории натуральных чисел с единицей, сложением и делимостью, доказанной независимо А. П. Бельтюковым и Л. Липшицем. К этой теме непосредственно примыкают вопросы выразимости с помощью отношений, которые можно определить в терминах сложения и делимости целых чисел. 
  
  Научная новизна.
  	В первой части работы будет введено понятие алгоритма квазиэлиминации кванторов (квази-ЭК), в некотором смысле обобщающее понятие алгоритма элиминации кванторов. Далее строятся два алгоритма квази-ЭК, которые формируют новое доказательство разрешимости экзистенциальной теории натуральных чисел с единицей, сложением и делимостью. Язык сложения и делимости достаточно богат и сложен для изучения; во второй главе понятие алгоритма квази-ЭК используется для получения результатов о выразимости с помощью более слабых средств. В третьей главе изучаются некоторые близкие проблемы выразимости.
chairman_dissertation_council.name: Александр
chairman_dissertation_council.surname: Охотин
chairman_dissertation_council.patronymic: Сергеевич
chairman_dissertation_council.position: Профессор Факультета математики и компьютерных наук СПбГУ
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Отсутствует
chairman_dissertation_council.wos_research_id: E-1385-2016
chairman_dissertation_council.scopus_author_id: 7004633256
chairman_dissertation_council.rinc_id: 928106
chairman_dissertation_council.orcid: 0000-0002-1615-2725
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Александр
organization_supervisor.surname: Гнетов
organization_supervisor.patronymic: Валентинович
organization_supervisor.position: Ученый секретарь СПбГУ
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.03.45
rubrics.name: Теория вычислимости
rubrics.code: 27.15.15
rubrics.name: Элементарная арифметика
rubrics.code: 27.03.66
rubrics.name: Математические структуры. Теория моделей
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Математическая логика, алгебра, теория чисел и дискретная математика
speciality_codes.code: 1.1.5.
supervisors.fio: Косовская Т.М.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Теоретические основы информатики
supervisors.responsible_type: Научный руководитель
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"
protection_organization.ogrn: 1037800006089
protection_organization.supervisor_name: НИКОЛАЙ
protection_organization.supervisor_surname: КРОПАЧЕВ
protection_organization.supervisor_patronymic: МИХАЙЛОВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Правительство Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"
author_organization.ogrn: 1037800006089
author_organization.supervisor_name: НИКОЛАЙ
author_organization.supervisor_surname: КРОПАЧЕВ
author_organization.supervisor_patronymic: МИХАЙЛОВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Правительство Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения