computability theory Concept
Preferred labels
en
- computability theory
de
- Berechenbarkeitstheorie
Alternative labels
en
- recursion theory
- theory of computability
de
- Berechenbarkeit
- Rekursionstheorie
Assigned collections
Broader terms
Narrower terms
Definition
de
Teilgebiet der theoretischen Informatik, das sich mit den formalen Grundlagen und den Grenzen der algorithmischen Methode befasst. Im Gegensatz zur Komplexitätstheorie steht die prinzipielle Berechenbarkeit einer Funktion im Vordergrund und nicht die Effizienz der Lösung. Eine zentrale Erkenntnis der Berechenbarkeitstheorie ist die Existenz unberechenbarer Funktionen (Halteproblem). (Hoffmann, Dirk W.: Theoretische Informatik. 2., aktualisierte Aufl. München : Hanser, 2011)