Berechenbarkeitstheorie Konzept
Bevorzugte Labels
en
- computability theory
de
- Berechenbarkeitstheorie
Alternative Labels
en
- recursion theory
- theory of computability
de
- Berechenbarkeit
- Rekursionstheorie
Zugewiesene Kollektionen
Allgemeinere Begriffe
Spezifischere Begriffe
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)