Berechenbarkeit

Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie). Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe reagiert. Der Definitionsbereich der Funktion ist die Menge der Eingaben, für die der Algorithmus eine Ausgabe produziert. Wenn der Algorithmus nicht terminiert, dann ist die Eingabe kein Element der Definitionsmenge. Dem Algorithmusbegriff liegt ein Berechnungsmodell zugrunde. Verschiedene Berechnungsmodelle sind entwickelt worden, es hat sich aber herausgestellt, dass die stärksten davon zum Modell der Turingmaschine gleich stark (Turing-mächtig) sind. Die Church-Turing-These behauptet daher, dass die Turingmaschinen den intuitiven Begriff der Berechenbarkeit wiedergeben. In der Berechenbarkeitstheorie heißen genau die Funktionen berechenbar, die Turing-berechenbar sind. Zu den Turing-mächtigen Berechnungsmodellen gehören neben der Turingmaschine beispielsweise Zweikellerautomaten, WHILE-Programme, μ-rekursiven Funktionen, Registermaschinen und der Lambda-Kalkül. Zu den Berechnungsmodellen, die schwächer sind als Turingmaschinen, gehören zum Beispiel die LOOP-Programme. Diese können zum Beispiel die Turing-berechenbare Ackermannfunktion nicht berechnen. Ein dem Begriff der Berechenbarkeit eng verwandter Begriff ist der der Entscheidbarkeit. Eine Teilmenge einer Menge (zum Beispiel eine Formale Sprache) heißt entscheidbar, wenn ihre charakteristische Funktion (im Wesentlichen das zugehörige Prädikat) berechenbar ist.

Wörter

Diese Tabelle zeigt das Beispiel für die Verwendung von Wortlisten zum Extrahieren von Stichwörtern aus dem obigen Text.

WortHäufigkeitAnzahl der ArtikelRelevanz
berechenbar5410.273
algorithmus56890.202
berechenbarkeit3350.166
funktion595540.135
berechnungsmodellen270.127

This website uses cookies to ensure you get the best experience on our website. Learn more. Got it.