name: Сложность вычислений на регистровых машинах со счётчиками
keyword_list: ИЕРАРХИЯ КЛИНИ-МОСТОВСКОГО КЛАССЫ ГЖЕГОРЧИКА РЕГИСТРОВЫЕ МАШИНЫ СО СЧЕТЧИКАМИ
abstract: В диссертации исследуется особый вид абстрактных вычислительных устройств — регистровые машины со счётчиками (RCмашины). Эти машины имеют специфическое устройство памяти: большая часть ячеек машины изменяется автономно, независимо от программы, а машина может изменять только одну ячейку. Цель работы — изучить вычислительные возможности RC-машин, сложность связанных с ними алгоритмических проблем, влияние различных модификаций на возможности RC-машин и применить RC-машины для получения новых результатов в теории рекурсивных функций. Работа имеет теоретический характер. Результаты работы обосновываются при помощи математических доказательств. В работе доказана универсальность RCмашин и охарактеризованы связанные с ними сложностные классы. Исследована возможность задания невычислимых функций с помощью RC-машин. С помощью арифметической иерархии охарактеризована сложность алгоритмических проблем, связанных с RCмашинами. Изучены различные модификации RC-машин. С помощью арифметизации RC-машин получены новые базисы по суперпозиции в некоторых классах рекурсивных функций. Все результаты являются новыми. Полученные результаты могут быть использованы в теории рекурсивных  функций для получения машинных и алгебраических описаний различных классов.
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: D-7271-2015
chairman_dissertation_council.scopus_author_id: 7004438484
chairman_dissertation_council.rinc_id: 2520
chairman_dissertation_council.orcid: 0000-0001-7773-8394
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Дмитрий
organization_supervisor.surname: Таюрский
organization_supervisor.patronymic: Альбертович
organization_supervisor.position: Проректор
organization_supervisor.territory: РОССИЯ
rubrics.code: 28.25.19
rubrics.name: Абстрактные машины
rubrics.code: 27.47.15
rubrics.name: Математическая теория управляющих систем
rubrics.code: 27.03.45
rubrics.name: Теория вычислимости
oecds.code: 01.01.UR
oecds.name: PHYSICS, MATHEMATICAL
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Марченков С. С.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: Вьюгин В. В.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
opponents.fio: Ямалеев М. М.
opponents.scientific_degree: Кандидат физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
protection_organization.short_name: ФГАОУ ВО "КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ", ФГАОУ ВО КФУ, КФУ, КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ, КАЗАНСКИЙ УНИВЕРСИТЕТ, КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"
protection_organization.ogrn: 1021602841391
protection_organization.supervisor_name: ИЛЬШАТ
protection_organization.supervisor_surname: ГАФУРОВ
protection_organization.supervisor_patronymic: РАФКАТОВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА, МГУ ИМЕНИ М.В.ЛОМОНОСОВА, МОСКОВСКИЙ УНИВЕРСИТЕТ ИЛИ МГУ
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА"
author_organization.ogrn: 1037700258694
author_organization.supervisor_name: ВИКТОР
author_organization.supervisor_surname: САДОВНИЧИЙ
author_organization.supervisor_patronymic: АНТОНОВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения