An oracle machine is an abstract machine used to study decision problems. It is a Turing machine with an additional black box, called an oracle, which can solve certain problems in one operation. The problem can be of any complexity class, even undecidable ones.

A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.