Kategorie:Theoretische Informatik

Die Theoretische Informatik beschäftigt sich mit der Frage, welche Probleme berechenbar oder unberechenbar sind und auf welche Weise sie berechnet werden können. Dazu verwendet man Berechnungsmodelle wie die Turingmaschine oder die Registermaschine, mathematische Kalküle wie den Lambda-Kalkül oder Befehlssätze wie WHILE und GOTO. Darauf aufbauend kann dann bewiesen werden, dass manche Probleme überhaupt nicht oder nicht mit vertretbarem Aufwand berechenbar sind.