Seminaria ogólnoinstytutowe:

Streszczenie (autorskie):

Matematycy badają struktury takie jak porządki, drzewa czy pierścienie. Teoria obliczeń zajmuję się trudnością obliczeniową obiektów przeliczalnych. Połączenie obydwu podejść prowadzi do obliczalnej teorii modeli, która bada związki między trudnością obliczeniową a strukturami w powyższym sensie. Struktury izomorficzne zwykle się utożsamia, jednak z obliczeniowego punktu widzenia przejście od danej struktury do jej izomorficznej kopii może znacząco wpłynąć na trudność obliczania niektórych relacji lub funkcji. Mając odpowiednio sformalizowane pojęcie trudności obliczeniowej, możemy zapytać, jaki jest zakres trudności obliczania danej relacji w obliczalnych kopiach ustalonej struktury. Pytanie to nazywa się problemem spektrum i wyznacza ono jeden z głównych kierunków badawczych obliczalnej teorii modeli. W referacie skupię się na problemie spektrum dla relacji obliczalnych na strukturze składającej się z liczb naturalnych i standardowego porządku. Dotychczasowe badania doprowadziły badaczy do wyodrębnienia w tym kontekście trzech rodzajów spektrów. Przez około dziesięć lat nie było wiadomo, czy podział ten jest wyczerpujący. W referacie omówię uzyskaną niedawno negatywną odpowiedź na to pytanie oraz szereg powiązanych wyników. Wykażę również ścisły związek tej problematyki z (częściowo filozoficznym) zagadnieniem notacji i algorytmicznego uczenia się. Referat będzie opierał się na moim artykule we współautorstwie z Nikolayem Bazhenovem i Michałem Wrocławskim (doi: 10.4230/LIPIcs.STACS.2022.8).