Berechnungsmodelle
Viele formale Rahmenwerke definieren, was es bedeutet zu rechnen, vom Funktions-Rewriting des Lambda-Kalküls bis hin zu Booleschen Schaltungen und Quantensystemen. Ein Vergleich ihrer Leistungsfähigkeit zeigt, welche Modelle äquivalent sind und welche sich tatsächlich unterscheiden.
Definition
Ein Berechnungsmodell ist ein präzises abstraktes Rahmenwerk, das festlegt, welche Operationen erlaubt sind und wie eine Berechnung abläuft; verschiedene Modelle können dieselbe Klasse von Funktionen berechnen, sich jedoch in Bezug auf Prägnanz, Parallelität oder die explizit gemachten Ressourcen unterscheiden.
Scope
Dieser Bereich umfasst den Lambda-Kalkül und funktionale Modelle, rekursive Funktionen und Registermaschinen, Boolesche Schaltungen und Schaltungskomplexität sowie Quantenberechnungen. Es wird untersucht, wie jedes Modell Algorithmen ausdrückt, wie ihre Berechenbarkeitsleistung durch die Church-Turing-These zusammenhängt und wie ihre Effizienz divergieren kann.
Sub-topics
Core questions
- Welche verschiedenen Möglichkeiten gibt es, den Begriff der Berechnung zu formalisieren?
- Welche Modelle sind in den Funktionen, die sie berechnen können, äquivalent und warum?
- Wie unterscheiden sich Modelle, wenn Effizienz, Parallelität oder physikalische Realisierbarkeit eine Rolle spielen?
- Kann ein physikalisch motiviertes Modell wie die Quantenberechnung die klassische Effizienz übertreffen?
Key theories
- Äquivalenz unter der Church-Turing-These
- Der Lambda-Kalkül, rekursive Funktionen, Registermaschinen und Turing-Maschinen berechnen alle genau dieselbe Klasse von Funktionen, die Konvergenz, die die Identifikation von Berechnung mit Turing-Berechenbarkeit begründet.
- Divergenz in der Effizienz
- Modelle, die in der Berechenbarkeit übereinstimmen, können sich stark in Bezug auf Ressourcen unterscheiden: Schaltungen legen parallele und nicht-uniforme Berechnungen offen, und Quantenmodelle scheinen Beschleunigungen zu bieten, sodass die Wahl des Modells für die Komplexität von großer Bedeutung ist, auch wenn dies für die Berechenbarkeit nicht der Fall ist.
Clinical relevance
Verschiedene Modelle beleuchten unterschiedliche Aspekte realer Berechnungen: Der Lambda-Kalkül ist die theoretische Grundlage funktionaler Programmiersprachen, Schaltungen modellieren Hardware und parallele Berechnungen, Registermaschinen spiegeln konventionelle Prozessoren wider, und Quantenmodelle leiten das Design aufkommender Quantenhardware und -algorithmen.
History
In den 1930er Jahren wurden der Lambda-Kalkül von Church, die rekursiven Funktionen von Gödel und Kleene sowie die Turing-Maschinen jeweils vorgeschlagen und dann als äquivalent erwiesen. Spätere Modelle fügten neue Dimensionen hinzu: Die Schaltungskomplexität formalisierte parallele und Hardware-Berechnungen, und Feynmans Vorschlag von 1982 zur Quantensimulation legte den Grundstein für das Quantenberechnungsmodell.
Key figures
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
Related topics
Seminal works
- church1936
- sipser2013
- aroraBarak2009
Frequently asked questions
- Warum sollte man viele Modelle studieren, wenn sie dieselben Funktionen berechnen?
- Die Äquivalenz gilt nur für das, was prinzipiell berechnet werden kann. Verschiedene Modelle erleichtern die Ausdrucksweise oder Analyse unterschiedlicher Dinge: Der Lambda-Kalkül verdeutlicht die funktionale Programmierung, Schaltungen zeigen Parallelität und Hardwarekosten auf, und Quantenmodelle erfassen physikalische Phänomene, sodass jedes die richtige Linse für unterschiedliche Fragen ist.
- Sind alle Berechnungsmodelle äquivalent?
- Alle vernünftigen klassischen Modelle berechnen dieselbe Klasse von Funktionen, was die Church-Turing-These stützt. Sie können sich jedoch stark in der Effizienz unterscheiden, und Modelle, die unterschiedliche Ressourcen nutzen, wie die Quanten-Superposition, können bestimmte Probleme schneller lösen, auch wenn sie dieselben Funktionen berechnen.