In der theoretischen Informaik geht es darum, zu zeigen, was man genau unter einem Algorithmus versteht, was mittels eines Computers überhaupt möglich ist und was nicht.

Der Einstieg in dieses Thema wird durch sogenannte Berechnungsmodelle gemacht: Für jedes Problem gibt es grundsätzlich eine Lösung (allwissendes Orakel), man muss nur schauen, dass man es mit den richtigen Hilfsmitteln, bzw in der richtigen Umgebung löst. Sobald man sich Einschränkungen hingibt (wie beispielsweise mathematischen Axiomen oder physikalischen Gesetzen), geht es sofort um die Fragen: was ist erlaubt, wo sind Grenzen, was ist unmöglich.

Leider leben wir in einer realen Welt, was bedeutet, dass wir von Begin an bestimmte Einschränkungen annehmen müssen, die einzige Einschränkung, die in der theoretischen Informaik jedoch gemacht wird, ist, dass ein Schritt einer Berechnung eine bestimmte Zeit benötigt (was eigentlich nichts anderes heisst, als dass unendlich viele Operationen auch unendlich lange dauern). Diese Einschränkung wird in der theoretischen Informatik beschrieben durch die Berechenbarkeit: Ein berechenbares Problem kann von einem Algorithmus in endlich vielen Schritten gelöst werden.

In den 30er-Jahren des zwazigsten Jahrhunderts setzten sich Emil Post, Alan Turing und Alonzo Church zusammen, um allgemein gültige Berechnungsmodelle aufgrund dieser Tatsache zu generieren. Diese sogenannt universellen Modelle stellten sich alle als äquivalent heraus, was bedeutet, dass mit jedem Berechnungsmodell, das sie aufstellten, zusammen mit unendlich viel Zeit und Speicherkapazität, jedes Problem, das berechenbar ist, lösbar wird.

Als Beispiel eines Berechnungsmodelles wird das der geometschischen Konstruktion genannt: Gegeben sind die Einschränkungen "Papier, Bleistift, Lineal und Zirkel" und die Definitionen "1"=eine Strecke mit fester, vorgegebener Länge, "0"=eine Strecke mit der Länge 0, "180°"=der Winkel des Halbkreises und "60°"=der Winkel eines Sechstel-Kreises.

Bewiesen ist, dass mit Strecken die mathematischen Operationen "+, -, *, /, Quadratwurzel" über rationale Zahlen simuliert werden können (Konstruktionen, siehe Script). Was ebenfalls möglich ist, ist die Addition, Subtraktion und Halbierung von Winkeln. Mittels diesen einfachen "Grundoperationen" können nun bereits eine Vielzahl an Berechnungen gelöst werden.

Beispielsweise ist es auch möglich, ein regelmässiges 5- und sogar 17-Eck zu konstruieren. Es gibt jedoch Dinge, die nicht möglich sind. Bekannte Beispiele sind die Kubikwurzel, das Dritteln eines Winkels und die Quadratur des Kreises.