Theorie der Berechnung

Eine künstlerische Darstellung von a Turing Maschine. Turing -Maschinen werden häufig als theoretische Modelle für die Computermodelle verwendet.

Im Theoretische Informatik und Mathematik, das Theorie der Berechnung ist der Zweig, der sich darum kümmert, welche Probleme auf a gelöst werden können Berechnungsmodellmit einem Algorithmus, wie effizient Sie können gelöst werden oder in welchem ​​Maße (z. B., ungefähre Lösungen gegenüber präzise). Das Feld ist in drei Hauptzweige unterteilt: Automatenheorie und formelle Sprachen, Computerbarkeitstheorie, und Computerkomplexitätstheorie, die durch die Frage verknüpft sind: "Was sind die grundlegenden Fähigkeiten und Grenzen von Computern?".^[1]

Um eine strenge Studie über Berechnungen durchzuführen, arbeiten Informatiker mit einer mathematischen Abstraktion von Computern, die als a genannt werden Berechnungsmodell. Es werden mehrere Modelle verwendet, aber die am häufigsten untersuchten ist die Turing Maschine.^[2] Informatiker untersuchen die Turing -Maschine, weil es einfach zu formulieren ist, analysiert und verwendet werden kann, um Ergebnisse zu beweisen, und weil sie das darstellen, was viele als das leistungsstärkste "vernünftige" Berechnungsmodell betrachten (siehe These der Kirche und tätige These).^[3] Es scheint, dass die potenziell unendliche Gedächtniskapazität ein nicht realisierbares Attribut ist, aber alle entschlossen Problem^[4] Von einer Turing -Maschine gelöst wird immer nur eine begrenzte Menge an Speicher erforderlich. Im Prinzip kann jedes Problem, das von einer Turing -Maschine gelöst (entschieden) gelöst werden kann, von einem Computer gelöst werden, der eine begrenzte Menge an Speicher hat.

Geschichte

Die Berechnungstheorie kann als die Erstellung von Modellen aller Art im Bereich der Informatik betrachtet werden. Deswegen, Mathematik und Logik werden verwendet. Im letzten Jahrhundert wurde es zu einer unabhängigen akademischen Disziplin und wurde von der Mathematik getrennt.

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

Geäst

Automatenheorie

Grammatik	Sprachen	Automat	Produktionsregeln (Einschränkungen)
Typ-0	Rekursiv aufgezählt	Turing Maschine	${\ displaystyle \ alpha \ rightarrow \ Beta}$ (keine Einschränkungen)
Typ 1	Kontextempfindlich	Linear-gebundene nicht deterministische Turing-Maschine	${\ displaystyle \ alpha a \ beta \ rightarrow \ alpha \ gamma \ beta}$
Typ 2	Kontextfrei	Nicht deterministisch Pushdown -Automaten	${\ displayStyle a \ rightarrow \ gamma}$
Typ-3	Regulär	Finite State Automaton	${\ displayStyle a \ rightarrow a}$ und ${\ displayStyle a \ rightarrow ab}$

Die Automatentheorie ist die Untersuchung abstrakter Maschinen (oder angemessener abstrakter „mathematischer“ Maschinen oder Systeme) und der Rechenprobleme, die mit diesen Maschinen gelöst werden können. Diese abstrakten Maschinen werden als Automaten bezeichnet. Automaten stammen aus dem griechischen Wort (αυτόματα), was bedeutet, dass etwas für sich etwas tut. Die Automatentheorie ist auch eng miteinander verbunden mit formelle Sprache Theorie,^[5] Da die Automata häufig nach der Klasse der formalen Sprachen klassifiziert werden, können sie erkennen. Ein Automat kann eine begrenzte Darstellung einer formalen Sprache sein, die ein unendlicher Satz sein kann. Automaten werden als theoretische Modelle für Computermaschinen verwendet und für Beweise zur Berechnung verwendet.

Formale Sprachtheorie

Setzen Sie Einschlüsse, die von der Chomsky -Hierarchie beschrieben werden

Die Sprachtheorie ist ein Zweig der Mathematik, der sich mit der Beschreibung von Sprachen als eine Reihe von Operationen über eine befasst Alphabet. Es ist eng mit der Automatentheorie verknüpft, da Automata verwendet wird, um formale Sprachen zu generieren und zu erkennen. Es gibt mehrere Klassen formaler Sprachen, die jeweils komplexere Sprachspezifikation ermöglichen als die zuvor, d. H. Chomsky -Hierarchie,^[6] und jede entspricht einer Klasse von Automata, die sie erkennt. Da Automaten als Berechnungsmodelle verwendet werden, sind formale Sprachen die bevorzugte Spezifikationsmodus für jedes Problem, das berechnet werden muss.

Computerbarkeitstheorie

Die Computerbarkeitstheorie befasst sich hauptsächlich mit der Frage, inwieweit ein Problem auf einem Computer lösbar ist. Die Aussage, dass die Problem stoppen kann nicht von einer Turing -Maschine gelöst werden^[7] ist eines der wichtigsten Ergebnisse in der Computerabilitätstheorie, da es ein Beispiel für ein konkretes Problem ist, das sowohl leicht zu formulieren als auch unmöglich zu lösen ist, indem sie eine Turing -Maschine haben. Ein Großteil der Berechnungsfähigkeitstheorie baut auf dem Anstaltproblemergebnis auf.

Ein weiterer wichtiger Schritt in der Computerbarkeitstheorie war Reis Satz, was angibt, dass für alle nicht trivialen Eigenschaften Teilfunktionen es ist, ist es unentscheidbar Ob eine Turing -Maschine eine Teilfunktion mit dieser Eigenschaft berechnet.^[8]

Die Computerabilitätstheorie ist eng mit dem Zweig von verwandt Mathematische Logik genannt Rekursionstheorie, wodurch die Beschränkung der Untersuchung von nur Berechnungsmodellen beseitigt wird, die auf das Turing -Modell reduzierbar sind.^[9] Viele Mathematiker und Computertheoretiker, die die Rekursionstheorie studieren, werden sie als Computerbarkeitstheorie bezeichnen.

Computerkomplexitätstheorie

Eine Darstellung der Beziehung zwischen Komplexitätsklassen

Komplexitätstheorie Überlegen Sie nicht nur, ob ein Problem auf einem Computer gelöst werden kann, sondern auch, wie effizient das Problem gelöst werden kann. Zwei Hauptaspekte werden berücksichtigt: Zeitkomplexität und Raumkomplexität, die je vielen Schritten unternehmen, um eine Berechnung durchzuführen, und wie viel Speicher für die Durchführung dieser Berechnung erforderlich ist.

Um zu analysieren, wie viel Zeit und Raum eine gegebene Algorithmus Erfordert, Informatiker drücken die Zeit oder den Raum aus, um das Problem als Funktion der Größe des Eingangsproblems zu lösen. Beispielsweise wird das Finden einer bestimmten Zahl in einer langen Liste von Zahlen schwieriger, wenn die Liste der Zahlen größer wird. Wenn wir sagen, gibt es n Zahlen in der Liste, wenn die Liste in keiner Weise sortiert oder indiziert ist, müssen wir uns möglicherweise jede Nummer ansehen, um die Nummer zu finden, die wir suchen. Wir sagen daher, dass der Computer eine Reihe von Schritten ausführen muss, die in der Größe des Problems linear wachsen, um dieses Problem zu lösen.

Um dieses Problem zu vereinfachen, haben Informatiker übernommen Big O Notation, was es ermöglicht, Funktionen so zu vergleichen, dass bestimmte Aspekte der Konstruktion einer Maschine nicht berücksichtigt werden müssen, sondern nur die asymptotisches Verhalten Wenn Probleme groß werden. In unserem vorherigen Beispiel könnten wir sagen, dass das Problem erfordert ${\ displayStyle o (n)}$ Schritte zur Lösung.

Vielleicht das wichtigste offene Problem in allen Informatik Ist die Frage, ob eine bestimmte breite Klasse von Problemen bezeichnet wird Np kann effizient gelöst werden. Dies wird weiter besprochen bei Komplexitätsklassen P und NP, und P gegen NP -Problem ist einer der sieben Millennium Prize Problems angegeben von der Clay Mathematics Institute im Jahr 2000. Die Offizielle Problembeschreibung wurde gegeben von Turing Award Gewinner Stephen Cook.

Berechnungsmodelle

Abgesehen von einem Turing Maschine, ein anderes Äquivalent (siehe: These der Kirche und tätige These) Berechnungsmodelle werden 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 eine endliche Abfolge von Lambda -Termen, die jeweils aus dem vorhergehenden Term durch eine Anwendung abgeleitet werden Beta -Reduktion.

Kombinationslogik

ist ein Konzept, das viele Ähnlichkeiten mit ${\ displayStyle \ lambda}$-Calculus, aber auch wichtige Unterschiede bestehen (z. B. Fixpunktkombinator Y hat eine normale Form in kombinatorischer Logik, aber nicht in ${\ displayStyle \ lambda}$-Infinitesimalrechnung). Die Kombinationslogik wurde mit großen Ambitionen entwickelt: das Verständnis der Natur von Paradoxien, die Grundlagen der Mathematik wirtschaftlicher (konzeptionell), wodurch der Begriff der Variablen beseitigt wird (so die Klärung ihrer Rolle in der Mathematik).

μ-rekursive Funktionen

Eine Berechnung besteht aus einer MU-rekursiven Funktion, d.h. Seine definierende Sequenz, jeder Eingabewert (n) und eine Folge rekursiver Funktionen, die in der Definitionssequenz mit Eingängen und Ausgängen erscheinen. Wenn also in der definierenden Sequenz einer rekursiven Funktion ${\ displayStyle f (x)}$ die Funktionen ${\ displayStyle g (x)}$ und ${\ displayStyle H (x, y)}$ Erscheinen, dann könnte die Form der Form 'g (5) = 7' oder 'H (3,2) = 10' erscheinen. Jeder Eintrag in dieser Sequenz muss eine Anwendung einer Grundfunktion sein oder aus den obigen Einträgen mit Verwendung folgen Komposition, primitive Rekursion oder μ Rekursion. Zum Beispiel wenn ${\ displayStyle f (x) = h (x, g (x))}$Dann müssen Begriffe wie 'G (5) = 6' und 'H (5,6) = 3' oben auftreten, damit 'f (5) = 3' erscheinen soll. Die Berechnung endet nur, wenn der endgültige Term den Wert der auf die Eingaben angewendeten rekursiven Funktion angibt.

Markov -Algorithmus

a String -Umschreibungssystem das verwendet Grammatik-ähnliche Regeln für den Betrieb Saiten von Symbolen.

Registrieren Sie Maschine

ist eine theoretisch interessante Idealisierung eines Computers. Es gibt mehrere Varianten. In den meisten von ihnen kann jedes Register eine natürliche Zahl (von unbegrenzter Größe) enthalten, und die Anweisungen sind einfach (und wenige in Anzahl), z. Es gibt nur eine Dekrementierung (kombiniert mit bedingter Sprung) und Inkrementierung (und Stoß). Das Fehlen des unendlichen (oder dynamisch wachsenden) externen Geschäfts (bei Turing -Maschinen) kann durch Ersetzen seiner Rolle durch verstanden werden Gödel -Nummerierung Techniken: Die Tatsache, dass jedes Register eine natürliche Zahl enthält Nummer theoretisch Fundamente dieser Techniken.

Zusätzlich zu den allgemeinen Computermodellen sind einige einfachere Rechenmodelle für spezielle, eingeschränkte Anwendungen nützlich. Reguläre AusdrückeGeben Sie beispielsweise String -Muster in vielen Kontexten an, von Office Productivity Software bis Programmiersprachen. Ein anderer Formalismus entspricht mathematisch mit regulären Ausdrücken, Finite Automaten werden im Schaltungsdesign und in einigen Arten von Problemlösungen verwendet. Kontextfreie Grammatiken Geben Sie die Programmiersprache Syntax an. Nicht deterministisch Pushdown -Automaten sind ein weiterer Formalismus, der kontextfreien Grammatiken entspricht. Primitive rekursive Funktionen sind eine definierte Unterklasse der rekursiven Funktionen.

Verschiedene Berechnungsmodelle können unterschiedliche Aufgaben erledigen. Eine Möglichkeit, die Leistung eines Computermodells zu messen, besteht darin, die Klasse von zu untersuchen formelle Sprachen dass das Modell erzeugen kann; in solchem ​​Weg zum Chomsky -Hierarchie von Sprachen wird erhalten.

Verweise

Weitere Lektüre

Lehrbücher, die sich an Informatiker richten

(Es gibt viele Lehrbücher in diesem Bereich; diese Liste ist zwangsläufig unvollständig.)

• Hopcroft, John E., und Jeffrey D. Ullman (2006). Einführung in die Automatentheorie, Sprachen und Berechnung. 3. Aufl Lesen, MA: Addison-Wesley. ISBN978-0-321-45536-9 Eine der Standardreferenzen im Feld.
• Linz P (2007). Eine Einführung in formelle Sprache und Automaten. Narosa Publishing. ISBN 9788173197819.
• Michael Sipser (2013). Introduction to the Theory of Computation (3. Aufl.). Cengage -Lernen. ISBN 978-1-133-18779-0.
• Eitan Gurari (1989). Eine Einführung in die Berechnungstheorie. Informatik Presse. ISBN 0-7167-8182-4. Archiviert von das Original Am 2007-01-07.
• Hein, James L. (1996) Theorie der Berechnung. Sudbury, MA: Jones & Bartlett. ISBN978-0-86720-497-1 Eine sanfte Einführung in das Feld, geeignet für Studenten des zweiten Studienjahres.
• Taylor, R. Gregory (1998). Modelle der Berechnung und formalen Sprachen. New York: Oxford University Press. ISBN978-0-19-510983-2 Ein ungewöhnlich lesbares Lehrbuch, das für Studenten der oberen Ebene oder anfängliche Absolventen geeignet ist.
• Lewis, F. D. (2007). Essentials der theoretischen Informatik Ein Lehrbuch, das die Themen formeller Sprachen, Automaten und Grammatiken abdeckt. Der Schwerpunkt scheint auf der Darstellung eines Überblicks über die Ergebnisse und ihre Anwendungen zu leisten, anstatt Beweise für die Ergebnisse zu liefern.
• Martin Davis, Ron Sigal, Elaine J. Weyuker, Berechnbarkeit, Komplexität und Sprachen: Grundlagen der theoretischen Informatik, 2. Aufl., Academic Press, 1994, ISBN0-12-206382-1. Deckt eine breitere Palette von Themen ab als die meisten anderen Einführungsbücher, einschließlich Programmsemantik und Quantifizierungstheorie. Ziel an Doktoranden.

Bücher zur Computerbarkeitstheorie aus der (breiteren) mathematischen Perspektive

• Hartley Rogers, Jr. (1987). Theorie der rekursiven Funktionen und effektiver Berechnbarkeit, MIT Press. ISBN0-262-68052-1
• S. Barry Cooper (2004). Computerbarkeitstheorie. Chapman und Hall/CRC. ISBN 1-58488-237-9..
• Carl H. Smith, Eine rekursive Einführung in die Theorie der Berechnung, Springer, 1994, ISBN0-387-94332-3. Ein kürzeres Lehrbuch für Doktoranden in Informatik.

Historische Perspektive

• Richard L. Epstein und Walter A. Carnielli (2000). Berechnbarkeit: Berechnbare Funktionen, Logik und die Grundlagen der Mathematik mit Computerbarkeit: Eine Zeitleiste (2. Aufl.). Wadsworth/Thomson Lernen. ISBN 0-534-54644-7..

Externe Links

• Theorie der Berechnung bei MIT
• Theorie der Berechnung bei Harvard
• Berechnungslogik - Eine Theorie der interaktiven Berechnung. Die Hauptnetzquelle zu diesem Thema.