Семинар ПОИС: Арифметика Пресбургера

На очередном заседании нашего семинара выступил научный сотрудник лаборатории Владислав Подымов. Тема его доклада: «Арифметика Пресбургера»

Арифметика Пресбургера — это теория целых неотрицательных чисел, в которой разрешено использовать только операцию сложения и предикат равенства чисел. На семинаре будут обсуждаться основные факты об этой теории: формальная сторона (арифметика как аксиоматическая теория первого порядка), содержательная сторона (выразительные возможности арифметики), разрешимость теории и нижняя оценка сложности.