Szanowni Państwo!

Serdecznie zapraszamy pracowników i studentów na seminarium Katedry Matematyki Dyskretnej i Teoretycznych Podstaw Informatyki, które odbędzie się w piątek 2 czerwca o godzinie 8.00 w sali A1/7.

Prelegent:
dr Katarzyna Grygiel (UJ)

Tytuł:
O losowych programach i ich własnościach

Streszczenie:
Od pewnego czasu można zaobserwować rosnące zainteresowanie ilościowymi badaniami w logikach i teorii obliczeń. Połączenie kombinatoryki i teorii obliczalności może wydawać się dość egzotyczne, jednak rozważane zagadnienia doprowadziły do powstania intrygujących matematycznych problemów, których rozwiązania znajdują zastosowania m.in. w weryfikacji oprogramowania i testowaniu kompilatorów.

Podczas referatu opowiem o kilku kombinatorycznych modelach dla logiki kombinatorów i rachunku lambda oraz przedstawię wyniki dotyczące własności (zarówno syntaktycznych, jak i semantycznych) losowych termów obu tych formalizmów. Pokażę również, dlaczego rozstrzyganie nierozstrzygalnych problemów (takich jak np. problem stopu) bywa czasami łatwiejsze niż rekurencyjne zliczanie skończonych obiektów.