Laboratory of Mathematical Logic at PDMI

Пятница, 14 сентября, комната 106. Начало в 19:00.

Докладчик: С. И. Николенко.

Тема: Полные комбинаторные односторонние функции.

Abstract

В докладе будут приведены конструкции всех известных на данный момент комбинаторных односторонних функций: предложенная в 2003 году Л.А.Левиным функция замощения доски доминошками, преобразование строк системами Туэ и функция, основанная на Post Correspondence Problem. Также будет доказана их полнота.

Доклад основан на совместной работе с А.Кожевниковым.