Seminaru za matematičku logiku i računarstvo

Na Seminaru za matematičku logiku i računarstvo, u ponedjeljak 2. studenoga 2026. u 17:15 sati, u predavaonici 105, PMF-MO, Teo Šestak održat će predavanje:

Realizabilnost i sintetička izračunljivost

Sažetak:  Realizabilnost je pristup u teoriji dokaza kojim se proučavaju konstruktivni dokazi. Počinjemo od apstraktnog modela izračunavanja, parcijalne kombinatorne algebre (eng. partial combinatory algebra, PCA), čiji elementi imaju ulogu realizirati formule neke formalne teorije, a zatim ćemo konstruirati kategoriju asemblera (eng. assembly) nad parcijalnom kombinatornom algebrom (na asembler gledamo kao na par skupa i informacija o izračunljivosti). U takvom ambijentu, primjenom kategoričke logike, asembleri nam daju modele konstruktivne logike.
Na kraju ćemo pokazati na koji način takav pristup možemo primijeniti u teoriji (ili teorijama) izračunljivosti, uvodom u tzv. sintetičku izračunljivost. Cilj seminara je, kao primjer, dokazati Postov teorem bez izravnog pozivanja na Turingove strojeve, parcijalno rekurzivne funkcije ili slične modele. Umjesto toga, iskoristit ćemo činjenice o asemblerima i koristiti konstruktivnu logiku.

Link za Zoom prijenos: https://zoom.us/j/99212592758?pwd=dfmNdu14N1nONLGwgv7Of64mrgoueK.1

(Meeting ID: 992 1259 2758    Passcode: 123456)