Berechnungstheorie - Theory of computation

Eine künstlerische Darstellung einer Turingmaschine . Turingmaschinen werden häufig als theoretische Rechenmodelle verwendet.

In der theoretischen Informatik und Mathematik ist die Berechnungstheorie der Zweig, der sich damit beschäftigt, welche Probleme an einem Berechnungsmodell mit einem Algorithmus gelöst werden können , wie effizient sie sich lösen lassen oder in welchem ​​Ausmaß (zB Näherungslösungen versus genaue Lösungen) ). Das Feld gliedert sich in drei Hauptzweige: Automatentheorie und formale Sprachen , Berechenbarkeitstheorie und Computational Complexity Theory , die durch die Frage verbunden sind: "Was sind die grundlegenden Fähigkeiten und Grenzen von Computern?".

Um eine gründliche Untersuchung der Berechnung durchzuführen, arbeiten Informatiker mit einer mathematischen Abstraktion von Computern, die als Berechnungsmodell bezeichnet wird . Es sind mehrere Modelle im Einsatz, aber das am häufigsten untersuchte ist die Turing-Maschine . Informatiker untersuchen die Turing-Maschine, weil sie einfach zu formulieren ist, analysiert und zum Beweis von Ergebnissen verwendet werden kann und weil sie das darstellt, was viele für das leistungsfähigste mögliche "vernünftige" Rechenmodell halten (siehe Church-Turing-These ). Es mag den Anschein haben, dass die potenziell unendliche Speicherkapazität ein nicht realisierbares Attribut ist, aber jedes entscheidbare Problem, das von einer Turing-Maschine gelöst wird, erfordert immer nur eine endliche Menge an Speicher. Im Prinzip kann also jedes Problem, das von einer Turingmaschine gelöst (entschieden) werden kann, von einem Computer mit endlicher Speicherkapazität gelöst werden.

Geschichte

Die Berechnungstheorie kann als die Erstellung von Modellen aller Art im Bereich der Informatik angesehen werden. Daher werden Mathematik und Logik verwendet. Im letzten Jahrhundert wurde sie zu einer eigenständigen akademischen Disziplin und wurde von der Mathematik getrennt.

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

Geäst

Automatentheorie

Grammatik Sprachen Automat Produktionsregeln (Einschränkungen)
Typ-0 Rekursiv aufzählbar Turing Maschine (keine Einschränkungen)
Typ 1 Kontextsensitiv Linearbegrenzte nichtdeterministische Turingmaschine
Typ 2 Kontextfrei Nicht-deterministischer Kellerautomat
Typ-3 Regulär Endlicher Automat
und

Automatentheorie ist das Studium abstrakter Maschinen (oder besser abstrakter "mathematischer" Maschinen oder Systeme) und der Rechenprobleme, die mit diesen Maschinen gelöst werden können. Diese abstrakten Maschinen werden Automaten genannt. Automata kommt vom griechischen Wort (Αυτόματα), was bedeutet, dass etwas etwas von selbst tut. Die Automatentheorie ist auch eng mit der formalen Sprachtheorie verwandt, da die Automaten oft nach der Klasse der formalen Sprachen klassifiziert werden, die sie erkennen können. Ein Automat kann eine endliche Darstellung einer formalen Sprache sein, die eine unendliche Menge sein kann. Automaten werden als theoretische Modelle für Rechenmaschinen verwendet und dienen zum Nachweis der Berechenbarkeit.

Theorie der formalen Sprache

Die Chomsky-Hierarchie
Set-Einschlüsse, die von der Chomsky-Hierarchie beschrieben werden

Die Sprachtheorie ist ein Zweig der Mathematik, der sich mit der Beschreibung von Sprachen als einer Menge von Operationen über ein Alphabet befasst . Sie ist eng mit der Automatentheorie verknüpft, da Automaten verwendet werden, um formale Sprachen zu generieren und zu erkennen. Es gibt mehrere Klassen formaler Sprachen, von denen jede eine komplexere Sprachspezifikation ermöglicht als die vorherige, dh die Chomsky-Hierarchie , und jede entspricht einer Klasse von Automaten, die sie erkennt. Da Automaten als Rechenmodelle verwendet werden, sind formale Sprachen die bevorzugte Spezifikationsmethode für jedes zu berechnende Problem.

Berechenbarkeitstheorie

Die Berechenbarkeitstheorie beschäftigt sich vor allem mit der Frage, inwieweit ein Problem auf einem Computer lösbar ist. Die Aussage, dass das Halteproblem nicht durch eine Turingmaschine gelöst werden kann, ist eines der wichtigsten Ergebnisse der Berechenbarkeitstheorie, da es ein Beispiel für ein konkretes Problem ist, das mit einer Turingmaschine sowohl leicht zu formulieren als auch unmöglich zu lösen ist. Ein Großteil der Berechenbarkeitstheorie baut auf dem Ergebnis des Halteproblems auf.

Ein weiterer wichtiger Schritt in der Berechenbarkeitstheorie war der Satz von Rice , der besagt, dass für alle nicht-trivialen Eigenschaften von Partialfunktionen unentscheidbar ist, ob eine Turing-Maschine eine Partialfunktion mit dieser Eigenschaft berechnet.

Die Berechenbarkeitstheorie ist eng mit dem als Rekursionstheorie bezeichneten Zweig der mathematischen Logik verwandt, der die Beschränkung aufhebt, nur Berechnungsmodelle zu studieren, die auf das Turing-Modell reduziert werden können. Viele Mathematiker und Computertheoretiker, die sich mit der Rekursionstheorie befassen, werden sie als Berechenbarkeitstheorie bezeichnen.

Rechnerische Komplexitätstheorie

Eine Darstellung der Beziehung zwischen Komplexitätsklassen

Die Komplexitätstheorie betrachtet nicht nur, ob ein Problem überhaupt 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 jeweils angeben, wie viele Schritte erforderlich sind, um eine Berechnung durchzuführen, und wie viel Speicher erforderlich ist, um diese Berechnung durchzuführen.

Um zu analysieren, wie viel Zeit und Platz ein bestimmter Algorithmus benötigt, drücken Informatiker den Zeit- oder Platzbedarf zur Lösung des Problems als Funktion der Größe des Eingabeproblems aus. Zum Beispiel wird es schwieriger, eine bestimmte Zahl in einer langen Liste von Zahlen zu finden, wenn die Liste von Zahlen größer wird. Wenn wir sagen, dass die Liste n Zahlen enthält, müssen wir , wenn die Liste in keiner Weise sortiert oder indiziert ist, jede Zahl untersuchen, um die gesuchte Zahl zu finden. Wir sagen also, dass der Computer zur Lösung dieses Problems eine Anzahl von Schritten ausführen muss, die mit der Größe des Problems linear anwächst.

Um dieses Problem zu vereinfachen, haben Informatiker die Big-O-Notation eingeführt , die es ermöglicht, Funktionen so zu vergleichen, dass keine besonderen Aspekte der Konstruktion einer Maschine berücksichtigt werden müssen, sondern nur das asymptotische Verhalten bei großen Problemen. In unserem vorherigen Beispiel könnten wir also sagen, dass das Problem Schritte zur Lösung erfordert .

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 weiter diskutiert , und das P-gegen-NP-Problem ist eines der sieben Millennium Prize-Probleme , die vom Clay Mathematics Institute im Jahr 2000 aufgestellt wurden. Die offizielle Problembeschreibung wurde vom Turing- Preisträger Stephen Cook gegeben .

Berechnungsmodelle

Abgesehen von einer Turing-Maschine werden andere äquivalente (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 .
Kombinatorische Logik
ist ein Konzept, das viele Ähnlichkeiten mit -Kalkül hat, aber es gibt auch wichtige Unterschiede (zB hat der Festkomma-Kombinator Y in der kombinatorischen Logik Normalform, aber nicht in -Kalkül). Die kombinatorische Logik wurde mit großen Ambitionen entwickelt: das Wesen von Paradoxien zu verstehen, die Grundlagen der Mathematik (konzeptionell) ökonomischer zu gestalten, den Begriff der Variablen zu eliminieren (und damit ihre Rolle in der Mathematik zu klären).
μ-rekursive Funktionen
eine Berechnung besteht aus einer mu-rekursiven Funktion, dh ihrer definierenden Folge, einem oder mehreren Eingabewerten und einer Folge von rekursiven Funktionen, die in der definierenden Folge mit Ein- und Ausgängen vorkommen. Wenn also in der Definitionsfolge einer rekursiven Funktion die Funktionen und vorkommen , können Terme der Form 'g(5)=7' oder 'h(3,2)=10' vorkommen. Jeder Eintrag in dieser Sequenz muss eine Anwendung einer Basisfunktion sein oder aus den obigen Einträgen folgen, indem Komposition , primitive Rekursion oder μ-Rekursion verwendet wird . Wenn zum Beispiel , dann müssen Begriffe wie 'g(5)=6' und 'h(5,6)=3' oben vorkommen, damit 'f(5)=3' erscheint. Die Berechnung endet nur, wenn der letzte Term den Wert der auf die Eingaben angewendeten rekursiven Funktion angibt.
Markov-Algorithmus
ein System zum Umschreiben von Zeichenfolgen , das grammatikähnliche Regeln verwendet, um mit Zeichenfolgen zu arbeiten .
Maschine registrieren
ist eine theoretisch interessante Idealisierung eines Computers. Es gibt mehrere Varianten. In den meisten von ihnen kann jedes Register eine natürliche Zahl (unbegrenzter Größe) enthalten, und die Befehle sind einfach (und nur wenige), zB existieren nur Dekrementierung (kombiniert mit bedingtem Sprung) und Inkrementierung (und Anhalten). Das Fehlen des unendlichen (oder dynamisch wachsenden) externen Speichers (wie bei Turing-Maschinen) kann verstanden werden, indem man seine Rolle durch Gödel-Nummerierungstechniken ersetzt : Die Tatsache, dass jedes Register eine natürliche Zahl enthält, ermöglicht die Darstellung einer komplizierten Sache (z Folge, oder einer Matrix usw.) durch eine entsprechende große natürliche Zahl — die Eindeutigkeit sowohl der Darstellung als auch der Interpretation kann durch zahlentheoretische Grundlagen dieser Techniken hergestellt werden.

Zusätzlich zu den allgemeinen Rechenmodellen sind einige einfachere Rechenmodelle für spezielle, eingeschränkte Anwendungen nützlich. Reguläre Ausdrücke beispielsweise spezifizieren Zeichenfolgenmuster in vielen Kontexten, von Office-Produktivitätssoftware bis hin zu Programmiersprachen . Ein weiterer Formalismus, der regulären Ausdrücken mathematisch äquivalent ist, sind endliche Automaten, die beim Schaltungsentwurf und bei einigen Arten der Problemlösung verwendet werden. Kontextfreie Grammatiken spezifizieren die Syntax von Programmiersprachen. Nichtdeterministische Kellerautomaten sind ein weiterer Formalismus, der kontextfreien Grammatiken entspricht. Primitive rekursive Funktionen sind eine definierte Unterklasse der rekursiven Funktionen.

Verschiedene Berechnungsmodelle haben die Fähigkeit, unterschiedliche Aufgaben zu erfüllen. Eine Möglichkeit, die Leistungsfähigkeit eines Rechenmodells zu messen, besteht darin, die Klasse der formalen Sprachen zu untersuchen , die das Modell erzeugen kann; auf diese Weise wird die Chomsky-Hierarchie der Sprachen erhalten.

Verweise

Weiterlesen

Lehrbücher für Informatiker

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

Bücher zur Berechenbarkeitstheorie aus der (weiteren) mathematischen Perspektive
Historische Perspektive

Externe Links