Theorie der Berechnung - Wikipedia

Eine künstlerische Darstellung einer Turingmaschine. Turingmaschinen werden häufig als theoretische Modelle für das Rechnen verwendet.

In der theoretischen Informatik und Mathematik beschäftigt sich die -Theorie mit der Frage, wie effizient Probleme auf einem Rechenmodell gelöst werden können ein Algorithmus. Das Feld ist in drei Hauptzweige unterteilt: Automatentheorie und -sprachen, Berechenbarkeitstheorie und Rechenkomplexitätstheorie, die mit der Frage verknüpft sind: "Was sind die grundlegenden Fähigkeiten und Einschränkungen von Computern?". ^[1]

In Reihenfolge Um eine gründliche Studie über Berechnungen durchzuführen, arbeiten Computerwissenschaftler mit einer mathematischen Abstraktion von Computern, die als Berechnungsmodell bezeichnet wird. Es werden mehrere Modelle verwendet, am häufigsten wird jedoch die Turing-Maschine untersucht. ^[2] Informatiker untersuchen die Turing-Maschine, weil sie einfach zu formulieren ist, analysiert werden kann und zum Nachweis der Ergebnisse verwendet werden kann und weil sie das darstellt, was viele davon berücksichtigen Möglichstes "vernünftiges" Berechnungsmodell (siehe Church-Turing-These). ^[3] Es scheint, dass die potenziell unendliche Speicherkapazität ein nicht realisierbares Attribut ist, aber jedes entscheidbare Problem ^[4] das von einer Turing-Maschine gelöst wird, wird immer nur erforderlich sein eine endliche Menge an Speicher. Im Prinzip kann jedes Problem, das von einer Turing-Maschine gelöst (entschieden) werden kann, von einem Computer gelöst werden, der über eine begrenzte Menge an Speicher verfügt.

Geschichte [ edit ]

Die Theorie der Berechnung kann als die Schaffung von Modellen aller Art auf dem Gebiet der Informatik betrachtet werden. Daher werden Mathematik und Logik verwendet. Im letzten Jahrhundert wurde sie zu einer unabhängigen akademischen Disziplin und wurde von der Mathematik getrennt.

Einige Pioniere der Rechentheorie waren die Alonzo-Kirche, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann und Claude Shannon.

Zweige [ edit ]

Automata-Theorie [ edit ]

Automaten-Theorie ist das Studium abstrakter Maschinen (oder besser geeignet, abstrakt.) "mathematische" Maschinen oder Systeme) und die Rechenprobleme, die mit diesen Maschinen gelöst werden können. Diese abstrakten Maschinen werden Automaten genannt. Automaten stammen aus dem griechischen Wort (Αυτόματα), was bedeutet, dass etwas von sich aus etwas tut. Die Automatentheorie ist auch eng mit der formalen Sprachtheorie verbunden, ^[5] da die Automaten häufig nach der Klasse der formalen Sprachen klassifiziert werden, die sie erkennen können. Ein Automat kann eine endliche Repräsentation einer Formsprache sein, die eine unendliche Menge sein kann. Automaten werden als theoretische Modelle für Rechenmaschinen und für Nachweise zur Berechenbarkeit verwendet.

Theorie der formalen Sprache [ edit ]

In der Chomsky-Hierarchie beschriebene Einschlüsse werden festgelegt.

Die Sprachtheorie ist ein Zweig der Mathematik, der sich mit der Beschreibung von Sprachen befasst Satz von Operationen über einem Alphabet. Es ist eng mit der Automatentheorie verbunden, da Automaten zur Generierung und Erkennung von formalen Sprachen verwendet werden. Es gibt mehrere Klassen formaler Sprachen, von denen jede eine komplexere Sprachspezifikation als die vorhergehende zulässt, d. H. Die Chomsky-Hierarchie ^[6] und jede entspricht einer Klasse von Automaten, die sie erkennt. Da Automaten als Modelle für die Berechnung verwendet werden, sind formale Sprachen die bevorzugte Art der Spezifikation für jedes Problem, das berechnet werden muss.

Berechenbarkeitstheorie [ edit ]

Die Berechenbarkeitstheorie beschäftigt sich hauptsächlich mit der Frage, inwieweit ein Problem auf einem Computer lösbar ist. Die Aussage, dass das Halteproblem nicht mit einer Turing-Maschine ^[7] gelöst werden kann, ist eines der wichtigsten Ergebnisse in der Theorie der Berechenbarkeit, da es ein Beispiel für ein konkretes Problem ist, das sowohl leicht zu formulieren als auch mit einer Turing-Maschine nicht zu lösen ist . Ein großer Teil der Theorie der Berechenbarkeit baut auf dem Ergebnis des Anhaltens des Problems auf.

Ein weiterer wichtiger Schritt in der Theorie der Berechenbarkeit war der Satz von Rice, der besagt, dass es für alle nicht trivialen Eigenschaften von Teilfunktionen unerheblich ist, ob eine Turing-Maschine eine Teilfunktion mit dieser Eigenschaft berechnet. ^{[8] [edit]}

Die Berechenbarkeitstheorie ist eng verwandt mit dem Zweig der mathematischen Logik, der Rekursionstheorie, der die Einschränkung des Studierens von nur auf das Turing-Modell reduzierbaren Berechnungsmodellen aufhebt. ^[9] Viele Mathematiker und Computertheoretiker, die sich auf Rekursionstheorie beziehen, werden sich darauf beziehen um es als Berechenbarkeitstheorie.

Rechnerische Komplexitätstheorie [ edit ]

Eine Darstellung der Beziehung zwischen Komplexitätsklassen

Die Komplexitätstheorie berücksichtigt nicht nur, ob ein Problem überhaupt auf einem Computer gelöst werden kann, sondern auch wie effizient das problem gelöst werden kann. Es werden zwei Hauptaspekte betrachtet: Zeitkomplexität und Raumkomplexität. Dies ist jeweils die Anzahl der Schritte, die zur Durchführung einer Berechnung erforderlich sind, und wie viel Speicherplatz zur Ausführung dieser Berechnung erforderlich ist.

Um zu analysieren, wie viel Zeit und Raum ein bestimmter Algorithmus benötigt, geben die Informatiker die zur Lösung des Problems erforderliche Zeit oder den erforderlichen Raum als Funktion der Größe des Eingangsproblems an. Das Auffinden einer bestimmten Nummer in einer langen Liste von Nummern wird beispielsweise schwieriger, wenn die Liste der Nummern größer wird. Wenn wir sagen, dass es n Zahlen in der Liste gibt, dann müssen wir, wenn die Liste auf keine Weise sortiert oder indiziert ist, jede Zahl betrachten, um die gesuchte Zahl zu finden. Wir sagen also, dass der Computer zur Lösung dieses Problems eine Reihe von Schritten ausführen muss, die mit der Größe des Problems linear wachsen.

Um dieses Problem zu vereinfachen, haben die Informatiker die Big-O-Notation verwendet, mit der Funktionen so verglichen werden können, dass bestimmte Aspekte der Konstruktion einer Maschine nicht berücksichtigt werden müssen, sondern nur das asymptotische Verhalten, wenn Probleme auftreten groß In unserem vorherigen Beispiel könnten wir also sagen, dass das Problem ${ displaystyle O (n)}$ Schritte erfordert lösen.

Das vielleicht wichtigste offene Problem in der gesamten Informatik ist die Frage, ob eine bestimmte breite Klasse von Problemen, die als NP bezeichnet werden, effizient gelöst werden kann. Dies wird in den Komplexitätsklassen P und NP ausführlicher besprochen. Das P versus NP-Problem ist eines der sieben Millennium-Preisprobleme, die das Clay Mathematics Institute im Jahr 2000 feststellte. Die offizielle Problembeschreibung wurde vom Turing-Preisträger Stephen Cook gegeben.

Berechnungsmodelle [ edit ]

Abgesehen von einer Turing-Maschine werden andere gleichwertige (Siehe: Church-Turing-These) Berechnungsmodelle verwendet.

Lambda-Kalkül

Eine Berechnung besteht aus einem anfänglichen Lambda-Ausdruck (oder zwei, wenn Sie die Funktion und ihre Eingabe trennen möchten) plus einer endlichen Folge von Lambda-Termen, die jeweils durch eine Anwendung der Beta-Reduktion aus dem vorhergehenden Term abgeleitet werden

Kombinatorik

ist ein Konzept, das viele Ähnlichkeiten mit ${\displaystyle \mathrm{\lambda \; <!--\; \lambda \; -->}}$ hat, aber es gibt auch wichtige Unterschiede (z. B. Fixpunkt) Kombinator Y hat eine normale Form in der Kombinationslogik, aber nicht in ${ displaystyle lambda}$ -calculus). Die kombinatorische Logik wurde mit großem Ehrgeiz entwickelt: das Verständnis der Natur von Paradoxien, die ökonomischere (konzeptionelle) Grundlagen der Mathematik, die Beseitigung des Begriffs der Variablen (wodurch ihre Rolle in der Mathematik geklärt wird).

μ-rekursive Funktionen

eine Berechnung besteht aus einer mu-rekursiven Funktion, dh seine definierende Reihenfolge, beliebige Eingabewerte und eine Folge von rekursiven Funktionen, die in der definierenden Reihenfolge mit Eingängen und Ausgängen erscheinen. Wenn also in der Definitionssequenz einer rekursiven Funktion ${\displaystyle f(x)}$ die Funktionen funktionieren ${Anzeigestil g (x)}$ und ${ displaystyle h (x, y)}$