Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Mittwoch, 26. Juli 2017 16:43 

Artikel zu dem Thema:

Theoretische Informatik


Thema durchsuchen:   

Startseite | Thema auswählen ]


Primitive Rekursion (Informatik)
mehr... (40 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 9202 mal gelesen
Der Begriff der Berechenbarkeit spielt neben dem der Komplexität in der klassischen theoretischen Informatik eine zentrale Rolle. Zunächst sollte man sich fragen, was das Adjektiv „berechenbar“ überhaupt bedeutet und worauf sich dieser Begriff bezieht. Intuitiv werden viele darunter wohl verstehen, dass etwas „sich errechnen lässt“ bzw. „vorhersehbar“ ist. Um jedoch etwas berechnen zu können benötigt man sicherlich ein Kochrezept, also einen Algorithmus bzw. eine Funktionsvorschrift. Schließlich müssen wir auch noch klären, was man alles berechnen kann, es wird sich nämlich zeigen, dass nicht alle Funktionen berechnenbar sind.

Sowohl Turing- als auch Registermaschinen sind Modelle von Maschinen. Sie nähern sich der Frage nach der Berechenbarkeit von der Seite der berechenbaren Automaten. Die jeweiligen Programme, welche auf diesen Maschinen laufen, müssen spezielle für das jeweilige Modell und die jeweilige Problemstellung zugeschnitten sein.

Einen hiervon differeten (aber äquivalenten) Zugang zur Frage der Berechenbarkeit besiert auf speziellen Funktionenklassen und darauf abgeschlossenen Operationen (Verknüpfungen). Mit den so genannte rekursiven Funktionen werden wir Lösungen von Problemen beschreiben und nicht, wie es bei den Maschinenmodellen üblich ist, die einzelnen Schritte des Rechenweges. Das Modell der rekursiven Funktionen versucht also nicht eine Maschine bzw. einen Automaten nachzubilden, sondern packt das Problem der Berechnbarkeit sozusagen bei der Wurzel, d.h. es nähert sich der Frage nach der Berechenbarkeit von Seite der Algorithmen.

Im Einzelnen werden behandelt:

  • Definition "intuitiv berechenbar"; Heranführung an den Begriff "Berechenbarkeit"; Grundlegende Definitionen
  • Nicht berechenbare Funktionen und deren Existenz; Beispiele und Beweis; Kardinalitätsargument;
  • Primitiv rekursive Funktionen; Induktionsprinzip; Basis-Funktionen; Grund-Funktionen; Konstante Funktionen; Nachfolgerfunktion (suc); Projektion auf den i-ten Eintrag; Substitution, Komposition, primitive Rekursion; primitiv rekursive Funktionen abgeschlossen gegenüber den Operationen; Beweis; Algorithmen; berechenbar;
  • Arithmetische Funktionen primitiv rekursiv dargestellt: Addition, Multiplikation, Potenzierung, modifizierte Subtraktion, Fakultät, Signum-Funktion, Maximum, Minimum, Identität; Abgeschlossen gegenüber Umordnung und Weglassen von Variablen; Fallunterscheidung;
  • Primitiv rekursive Relationen: Prädikate, Und, Oder, Nicht, Kleinergleich, Größergleich, Gleichheit; Charakteristische Funktion
  • Der unbeschränkte mue-Operator; echte Erweiterung der primitiv rekursiven Funktionen; alle berechenbaren Funktionen; Minimalisierung; beschränkte mue-Operator; Beispiele;
  • Ackermannfunktion; wichtigsten Charakterisierungen; Eigenschaften; Beweise; streng monoton in beiden Argumenten; wächst stärker als jede primitiv rekursive Funktion.
Geschrieben von Alexander am Mittwoch, 17. Januar 2007 mehr...


Umfrage
Ganz klar, das schönste Ressort der Mathematik ist die

Zahlentheorie
(Lineare) Algebra
Topologie, Maßtheorie, Integrationstheorie
Statistik, Wahrscheinlichkeitstheorie, Stochastik
Analysis, Funktionalanalysis
Funktionentheorie
Kombinatorik, Graphentheorie
Diskrete Mathematik
Lineare Optimierung

Ergebnisse
Stimmen: 667
Kommentare: 0
Umfragen

Login
Benutzername:

Passwort:



Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.0724 Sekunden, mit 51 Datenbank-Abfragen