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?
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?