The things you directly need are algorithmic complexity theory (Classic textbook: Li and Vitanyi) and some way of understanding proofs (Probably start with regular mathematical logic / model theory, not sure of a standout textbook here, maybe Manin?, then look into modal logic, classic textbook by Boolos).

Prerequisites for those are mathematical logic, set theory, probability theory, and some amount of discrete math.