Mit jelent az igazság fogalma, és mik azok a szemantikai modellek, amelyeken ezt a fogalmat értelmezni tudjuk? Vajon a logika segítségével minden eldöntendő kérdésre választ kaphatunk? Vannak-e korlátai a logikának? Mivel foglalkozik a bizonyításelmélet, és mit állít az úgynevezett teljességi tétel a logika erejéről? Pontosan miről szólnak, és miért rengették meg a matematika építményének alapjait Kurt Gödel híres nemteljességi tételei?
Hogyan tudjuk az algoritmikus problémák nehézségét összehasonlítani egymással? Mit nevezünk Karp-redukciónak és mikor mondjuk egy problémára, hogy NP-nehéz? Kicsoda Babai László és mi a jelentősége 2015-ös felfedezésének? Alice és Bob valóban biztonságban érezheti magát?
Mit jelent az, hogy “algoritmus”? Minden feladat megoldható algoritmussal? Mik azok a formális nyelvek? Mikor mondjuk egy problémára, hogy algoritmikusan kiszámíthatatlan vagy eldönthetetlen? Mik az algoritmikus eldönthetőség határai?
