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)

Notationen

Verwandte Begriffe

Beziehungen zu anderen Ontologien

Close Matches

Exact Matches

Related Matches

Broader Matches

Narrower Matches

Änderungsanmerkungen

Redaktionelle Anmerkungen

Beispiele

Geschichtliche Anmerkungen

Bereichsanmerkungen