Vollständigkeit

Für die Verwendung dieses Begriffs in der Theorie der relativen Berechnung durch Oracle -Maschinen siehe Turing Reduktion.

Im Computerbarkeitstheorie, ein System von Datenmanipulationsregeln (z. B. die eines Computers Befehlssatz, a Programmiersprache, oder ein Mobilfunkautomat) wird gesagt, dass Turing-Complete oder rechnerisch universell Wenn es verwendet werden kann, um alle zu simulieren Turing Maschine (Entwickelt von englischer Mathematiker und Informatiker Alan Turing). Dies bedeutet, dass dieses System andere Daten-Manipulations-Regelsätze erkennen oder entscheiden kann. Die Vollständigkeit wird verwendet, um die Leistung eines solchen Datenmanipulations-Regelsatzes auszudrücken. Praktisch alle Programmiersprachen sind heutzutage zu vervollständigen.

Ein verwandtes Konzept ist das von Turing -Äquivalenz- Zwei Computer P und Q werden als gleichwertig bezeichnet, wenn P q simulieren kann, und q kann P. die simulieren können These der Kirche und tätige These Vermutungen, dass jede Funktion, deren Werte von einem berechnet werden können Algorithmus Kann von einer Turing-Maschine berechnet werden, und daher, wenn ein realer Computer eine Turing-Maschine simulieren kann, ist er einem Turing-Computer entsprechend. EIN Universelle Turing -Maschine Kann verwendet werden, um jede Turing-Maschine und damit die rechnerischen Aspekte eines möglichen realen Computers zu simulieren.[NB 1]

Um zu zeigen, dass etwas vervollständigt ist, reicht es aus, zu zeigen, dass es verwendet werden kann, um ein Turing-Complete-System zu simulieren. Kein physikalisches System kann unendlichem Gedächtnis haben, aber wenn die Einschränkung des endlichen Gedächtnisses ignoriert wird, sind die meisten Programmiersprachen ansonsten abgeschlossen.

Nicht-mathematische Verwendung

Im umgangssprachlich Die Verwendung, die Begriffe "Turing-Complete" und "Turing-äquivalent" werden verwendet, um, dass jede reale allgemeine Computer- oder Computersprache die rechnerischen Aspekte eines anderen Computers oder Computersprache mit realer Welt annähernd simulieren kann . Im wirklichen Leben führt dies zu den praktischen Konzepten des Computers Virtualisierung und Emulation.

Bisher konstruierte reale Computer können funktionell wie eine einzelne Turing-Maschine analysiert werden (das "Band", das ihrem Speicher entspricht); Somit kann die zugehörige Mathematik gelten, indem sie ihren Betrieb weit genug abstrahieren. Reale Computer haben jedoch nur begrenzte physische Ressourcen, so dass sie es nur sind linear begrenzter Automaten Komplett. Dagegen a Universeller Computer wird als Gerät mit einem Turing-Completen-Befehlssatz, dem unendlichen Speicher und einer unendlichen verfügbaren Zeit definiert.

Formale Definitionen

Im Computerbarkeitstheorie, werden mehrere eng verwandte Begriffe verwendet, um die Rechenleistung eines Rechensystems zu beschreiben (wie z. abstrakte Maschine oder Programmiersprache):

Vollständigkeit
Ein Rechensystem, das jede Turing berechnen kann.berechnungsbare Funktion wird als Turing-Complete (oder Turing-Kraft) bezeichnet. Alternativ ist ein solches System eines, das a simulieren kann Universelle Turing -Maschine.
Turing -Äquivalenz
Ein Turing-Complete-System wird als Turing-äquivalent bezeichnet, wenn jede Funktion, die es berechnen kann, auch Turing-CORPIEL ist. d.h. Turing -Maschinen. Alternativ kann ein turäquivalentes System eines universellen Maschine simulieren und simuliert werden. (Alle bekannten physikalisch implementierbaren Turing-Completen-Systeme sind turäquivalent, was die Unterstützung des These der Kirche und tätige These.))
(Rechnerische) Universalität
Ein System wird in Bezug auf eine Systemklasse als universell bezeichnet, wenn es jede Funktion berechnen kann, die von Systemen in dieser Klasse berechnet werden kann (oder jedes dieser Systeme simulieren kann). Typischerweise wird der Begriff "Universalität" stillschweigend in Bezug auf eine turbetonische Systemklasse verwendet. Der Begriff "schwach universell" wird manchmal verwendet, um ein System zu unterscheiden (z. B. a Mobilfunkautomat) deren Universalität nur durch Änderung der Standarddefinition von erreicht wird Turing Maschine um Eingabeströme mit unendlich vielen 1s einzuschließen.

Geschichte

Die Vollständigkeit ist insofern von Bedeutung, als jedes reale Design für ein Computergerät durch a simuliert werden kann Universelle Turing -Maschine. Das These der Kirche und tätige These gibt an, dass dies ein Gesetz der Mathematik ist - dass eine universelle Turing -Maschine im Prinzip jede Berechnung durchführen kann, die jedes andere programmierbare Computer kann. Dies sagt nichts über die Anstrengungen aus, die erforderlich sind, um das zu schreiben Programm, oder die Zeit, die die Maschine benötigt, um die Berechnung auszuführen, oder die Fähigkeiten, die die Maschine besitzt, die nichts mit Berechnung zu tun haben.

Charles Babbage's analytischer Motor (1830er Jahre) wäre die erste Turing-Complete-Maschine gewesen, wenn sie zum Zeitpunkt des Entwurfs gebaut worden wäre. Babbage schätzte es, dass die Maschine großartige Berechnungsleistungen, einschließlich primitives logisches Denken, in der Lage war, aber er schätzte es nicht, dass keine andere Maschine besser abschneiden konnte. Von den 1830er Jahren bis in die 1940er Jahre wurden mechanische Berechnungsmaschinen wie Addierer und Multiplikatoren gebaut und verbessert, konnten jedoch keinen bedingten Zweig ausführen und waren daher nicht abgeschlossen.

Im späten 19. Jahrhundert, Leopold Kronecker formulierte Berechnungsvorstellungen, Definition primitive rekursive Funktionen. Diese Funktionen können durch rote Berechnung berechnet werden, aber sie reichen nicht aus, um einen universellen Computer zu erstellen, da die Anweisungen, die sie berechnen, keine unendliche Schleife zulassen. Anfang des 20. Jahrhunderts, David Hilbert führte ein Programm an, um alle Mathematik mit präzisen Axiomen und präzisen logischen Abzugsregeln zu axiomatisieren, die von einer Maschine durchgeführt werden könnten. Bald wurde klar, dass eine kleine Reihe von Abzugsregeln ausreicht, um die Folgen von Axiomen zu erzielen. Diese Regeln wurden von bewiesen von Kurt Gödel 1930 genug, um jeden Satz zu produzieren.

Der tatsächliche Begriff der Berechnung wurde bald darauf isoliert, beginnend mit Gödels Unvollständigkeitstheorem. Dieser Satz zeigte, dass Axiomsysteme begrenzt waren, wenn sie über die Berechnung argumentieren, die ihre Theoreme abzieht. Kirche und Turing unabhängig voneinander zeigten, dass Hilbert's Entscheidungsproblem (Entscheidungsproblem) war unlösbar,[1] So identifizieren Sie den Rechenkern des Unvollständigkeitssatzes. Diese Arbeit zusammen mit Gödels Arbeit an Allgemeine rekursive Funktionen, stellte fest, dass es Sätze einfacher Anweisungen gibt, die bei Zusammensetzung in der Lage sind, Berechnungen zu erstellen. Die Arbeit von Gödel zeigte, dass der Begriff der Berechnung im Wesentlichen einzigartig ist.

1941 Konrad Zuse abgeschlossen Z3 Computer. Zuse war mit Turings Arbeit zu dieser Zeit nicht vertraut. Insbesondere fehlten dem Z3 engagierte Einrichtungen für einen bedingten Sprung, wodurch er nicht abgeschlossen war. 1998 wurde jedoch von Rojas gezeigt, dass der Z3 in der Lage ist, bedingte Sprünge zu simulieren und daher theoretisch vollständig zu treiben. Dazu müsste sein Bandprogramm lang genug sein, um jeden möglichen Weg durch beide Seiten jedes Zweigs durchzuführen.[2]

Der erste Computer, der in der Praxis in der Lage ist, in der Praxis zu verzweigen und daher in der Praxis vollständig zu erfüllen, war die Eniac im Jahr 1946. Zuus Z4 Der Computer war 1945 in Betrieb, unterstützte jedoch erst 1950 die bedingte Verzweigung.[3]

Computerbarkeitstheorie

Computerbarkeitstheorie Verwendet Berechnungsmodelle Probleme analysieren und feststellen, ob sie es sind berechenbar und unter welchen Umständen. Das erste Ergebnis der Computerbarkeitstheorie ist, dass es Probleme gibt, für die es unmöglich ist, vorherzusagen, was ein (Turing-Complete) System über einen willkürlich langen Zeitpunkt tun wird.

Das klassische Beispiel ist das Problem stoppen: Erstellen Sie einen Algorithmus, der als Eingabe eines Programms in einer Turing-Complete-Sprache und einigen Daten zugeführt wird das Programm und bestimmt, ob das Programm, das mit der Eingabe arbeitet, letztendlich anhalten oder für immer fortgesetzt werden. Es ist trivial, einen Algorithmus zu erstellen, der dies kann etwas Eingaben, aber unmöglich, dies im Allgemeinen zu tun. Für jedes Merkmal der eventuellen Ausgabe des Programms ist es unmöglich zu bestimmen, ob diese Eigenschaft gelten wird.

Diese Unmöglichkeit hat Probleme bei der Analyse realer Computerprogramme. Beispielsweise kann man kein Tool schreiben, das Programmierer vollständig vor dem Schreiben von unendlichen Schleifen schützt oder Benutzer vor Eingaben schützt, die unendliche Schleifen verursachen würden.

Man kann stattdessen ein Programm auf nur für einen festen Zeitraum ausführen (Auszeit) oder begrenzen Sie die Leistung von Durchflusskontrollanweisungen (z. B. nur Schleifen bereitstellen, die die Elemente eines vorhandenen Arrays iterieren). Ein weiterer Satz zeigt jedoch, dass es Probleme gibt, die durch Turing-Abschlusssprachen lösbar sind, die von keiner Sprache mit nur endlichen Schleifenfähigkeiten gelöst werden können (d. H. Jede Sprache, die garantiert, dass jedes Programm letztendlich zum Stillstand kommt). Eine solche Sprache ist also nicht abgeschlossen. Beispielsweise wird eine Sprache, in der Programme garantiert abgeschlossen sind, und der Anhalten kann die von berechnungsfähige Funktion nicht berechnen, die von erstellt wurde, Cantors diagonales Argument Bei allen rechenbaren Funktionen in dieser Sprache.

Turing Orakel

Hauptartikel: Oracle Machine

Ein Computer mit Zugriff auf ein unendliches Datenband kann leistungsfähiger sein als eine Turing -Maschine: Zum Beispiel kann das Band die Lösung für die Lösung enthalten Problem stoppen oder ein anderes Turing-abschließbares Problem. Ein solches unendliches Datenband wird als a genannt Turing Oracle. Auch ein Turing Oracle mit zufälligen Daten ist nicht berechnet (mit Wahrscheinlichkeit 1), da es nur zählich viele Berechnungen gibt, aber unzählige Orakel. Ein Computer mit einem zufälligen Turing -Oracle kann also Dinge berechnen, die eine Turing -Maschine nicht kann.

Digitale Physik

Siehe auch: These der Kirche und thesis § philosophische Implikationen

Alle bekannten Gesetze der Physik haben Konsequenzen, die durch eine Reihe von Annäherungen auf einem digitalen Computer berechnet werden. Eine Hypothese genannt Digitale Physik gibt an, dass dies kein Zufall ist, weil die Universum selbst ist auf einer universellen Turing -Maschine berechnet. Dies würde bedeuten, dass kein Computer, der leistungsfähiger ist als eine universelle Turing -Maschine, physisch erstellt werden kann.

Beispiele

Die Computersysteme (Algebren, Kalkül), die als Turing-Complete-Systeme diskutiert werden Theoretische Informatik. Sie sollen so einfach wie möglich sein, so dass es einfacher wäre, die Berechnungsgrenzen zu verstehen. Hier sind ein paar:

Die meisten Programmiersprachen (Ihre abstrakten Modelle, möglicherweise mit einigen bestimmten Konstrukten, die das endliche Gedächtnis weggelassen haben), konventionelle und unkonventionelle, sind abgeschlossen. Das beinhaltet:

Etwas Schreiben Sie Systeme neu sind Turing-Complete.

Die Vollständigkeit ist eine abstrakte Fähigkeitserklärung und nicht eine Rezept für spezifische Sprachmerkmale, die zur Implementierung dieser Fähigkeit verwendet werden. Die Funktionen, die zur Erreichung der Vollständigkeit verwendet werden, können sehr unterschiedlich sein. Forran Systeme würden Schleifenkonstrukte oder möglicherweise sogar sogar verwenden gehe zu Aussagen zur Wiederholung; Haskell und Prolog, der fast vollständig Schleifen fehlt, würde verwenden Rekursion. Die meisten Programmiersprachen beschreiben Berechnungen auf Von Neumann -Architekturen, die Speicher (RAM und Register) und eine Steuereinheit haben. Diese beiden Elemente machen diese Architektur zum Turing. Sogar rein Funktionssprachen sind Turing-Complete.[5][NB 2]

Vollständigkeit der deklarativen Vollständigkeit Sql wird durch implementiert rekursive gemeinsame Tabellenausdrücke.[6] Es überrascht nicht, dass prozedurale Erweiterungen gegen SQL (Plsqlusw.) sind auch turbetrieben. Dies zeigt einen Grund, warum relativ leistungsstarke Sprachen ohne Turing selten sind: Je leistungsstärker die Sprache anfangs ist, desto komplexer sind die Aufgaben, auf die sie angewendet wird und je früher ihre mangelnde Vollständigkeit als Nachteil wahrgenommen wird, wodurch sie ermutigt, ihre Förderung zu ermutigen, um sie zu fördern Erweiterung bis es Turing-Complete ist.

Die Untyped Lambda -Kalkül ist Turing-Complete, aber viele typisierte Lambda-Kalkül, einschließlich System f, sind nicht. Der Wert typisierter Systeme basiert auf ihrer Fähigkeit, die meisten typischen Computerprogramme darzustellen und gleichzeitig mehr Fehler zu erkennen.

Regel 110 und Conways Leben des Lebens, beide Mobilfunk Automaten, sind abgeschlossen.

Unbeabsichtigte Vollständigkeit

Einige Spiele und andere Software sind zufällig abgeschlossen, d. H. Nicht vom Design.

Software:

Videospiele:

Sozialen Medien:

Rechensprachen:

Computerhardware:

  • x86 MOV -Anweisung[15]

Biologie:

Nicht-Turing-Abschlusssprachen

Es gibt viele Rechensprachen, die nicht abgeschlossen sind. Ein solches Beispiel ist der Satz von reguläre Sprachen, die von generiert werden von Reguläre Ausdrücke und die anerkannt werden von Finite Automaten. Eine leistungsstärkere, aber immer noch nicht abgeschlossene Erweiterung der endlichen Automaten ist die Kategorie von Pushdown -Automaten und Kontextfreie Grammatiken, die üblicherweise zur Erzeugung von Bäumen in einer ersten Programmphase verwendet werden Kompilieren. Weitere Beispiele sind einige der frühen Versionen der in die Pixel -Shader -Sprachen eingebetteten Sprachen Direct3d und OpenGL Erweiterungen.

Im Gesamtfunktionalprogrammierung Sprachen wie Wohltätigkeit und EpigrammAlle Funktionen sind total und müssen enden. Wohltätigkeit verwendet ein Typsystem und Kontrollkonstrukte bezogen auf Kategoriestheorie, während Epigramm verwendet abhängige Typen. Das SCHLEIFE Die Sprache ist so konzipiert, dass sie nur die Funktionen berechnet, die sind primitive rekursiv. Alle diese berechnen die ordnungsgemäßen Teilmengen der gesamten rechenbaren Funktionen, da der gesamte Satz der gesamten berechnbaren Funktionen nicht ist rechenbar aufzählbar. Auch da alle Funktionen in diesen Sprachen total sind, Algorithmen für rekursiv aufzählbare Sätze Kann nicht in diesen Sprachen geschrieben werden, im Gegensatz zu Turing -Maschinen.

Obwohl (nicht typed) Lambda -Kalkül ist Turing-Complete, Einfach tippte Lambda -Kalkül ist nicht.

Siehe auch

Anmerkungen

  1. ^ Ein UTM kann nicht-komputationelle Aspekte wie z. I/o.
  2. ^ Das folgende Buch enthält eine Einführung für Berechnungsmodelle: Rauber, Thomas; Rünger, Gudula (2013). Parallele Programmierung: Für Multicore- und Cluster -Systeme (2. Aufl.). Springer. ISBN 9783642378010.

Verweise

  1. ^ Hodges, Andrew (1992) [1983], Alan Turing: Das Rätsel, London: Burnett Books, p. 111, ISBN 0-04-510060-8
  2. ^ Rojas, Raul (1998). "Wie man Zuss Z3 zu einem universellen Computer macht". Annalen der Geschichte des Computers. 20 (3): 51–54. doi:10.1109/85.707574.
  3. ^ Rojas, Raúl (1. Februar 2014). Google Übersetzung, PDF ist auch übersetzbar. "Konrad Zuse und der Bedingte Sprung" [Konrad Zuuse und der bedingte Sprung]. Informatik-Spektrum (auf Deutsch). 37 (1): 50–53. doi:10.1007/s00287-013-0717-9. ISSN 0170-6012. S2CID 1086397. {{}}: Externer Link in |others= (Hilfe)
  4. ^ Lyons, Bob (30. März 2001). "Universelle Turing -Maschine in XSLT". B2B -Integrationslösungen von Unidex. Archiviert Aus dem Original am 17. Juli 2011. Abgerufen 5. Juli 2010.
  5. ^ Boyer, Robert S.; Moore, J. Strother (Mai 1983). Ein mechanischer Beweis für die Vollständigkeit von reinem Lisp (PDF) (Technischer Bericht). Institut für Computing Science, Universität von Texas in Austin. 37. Archiviert (PDF) Aus dem Original am 22. September 2017.
  6. ^ Dfetter; Breinbaas (8. August 2011). "Cyclic Tag System". PostgreSQL Wiki. Abgerufen 10. September 2014.
  7. ^ "Ankündigung von Lambda: Verwandeln Sie Excel -Formeln in benutzerdefinierte Funktionen". TechCommunity.microsoft.com. 3. Dezember 2020. Abgerufen 8. Dezember 2020.
  8. ^ Walenhain, Tom (9. April 2020). "Über die Vollständigkeit von Frau Powerpoint" (PDF).[selbstveröffentlichte Quelle]
  9. ^ Cedotal, Andrew (16. April 2010). "Man nutzt das schwierigste Computerspiel der Welt, um ... eine funktionierende Turing -Maschine zu kreieren.". Die Mary Sue. Archiviert Aus dem Original am 27. Juni 2015. Abgerufen 2. Juni 2015.
  10. ^ Plunkett, Luke (16. Juli 2019). "Städte: Skylines-Karte wird zum kotbetriebenen Computer". Kotaku. Abgerufen 16. Juli 2019.
  11. ^ Caldwell, Brendan (20. November 2017). "Opus Magnum Player macht einen alchemischen Computer". Rockpapier -Schrotflinte. Abgerufen 23. September 2019.
  12. ^ Schriftsteller, Mitarbeiter. "Dieser in Minecraft gebaute 8-Bit-Prozessor kann seine eigenen Spiele durchführen". PC Welt. Abgerufen 21. Juli 2022.
  13. ^ "Habbos Twitter -Thread zur Implementierung eines Turing -Maschine im Spiel". 9. November 2020. Abgerufen 11. November 2020.
  14. ^ Meyers, Scott (Scott Douglas) (2005). Effektives C ++: 55 spezifische Möglichkeiten zur Verbesserung Ihrer Programme und Designs (3. Aufl.). Upper Saddle River, NJ: Addison-Wesley. ISBN 0321334876. OCLC 60425273.
  15. ^ Dolan, Stephen. "MOV ist Turing-Complete" (PDF). stedolan.net. Archiviert von das Original (PDF) am 14. Februar 2021. Abgerufen 9. Mai 2019.
  16. ^ Shah, Shalin; Wee, Jasmine; Lied, Tianqi; Ceze, Luis; Strauss, Karin; Chen, Yuan-Jyue; Reif, John (4. Mai 2020). "Verwenden von Strangverdrängernpolymerase zu chemischen Reaktionsnetzwerken". Zeitschrift der American Chemical Society. 142 (21): 9587–9593. doi:10.1021/jacs.0c02240. ISSN 0002-7863. PMID 32364723. S2CID 218504535.
  17. ^ Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (Oktober 2013). "Programmierbare chemische Controller aus DNA". Natur Nanotechnologie. 8 (10): 755–762. Bibcode:2013natna ... 8..755c. doi:10.1038/nnano.2013.189. ISSN 1748-3395. PMC 4150546. PMID 24077029.
  18. ^ Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (15. Dezember 2017). "Enzymfreie Nukleinsäuredynamische Systeme". Wissenschaft. 358 (6369): EAAL2052. doi:10.1126/science.aal2052. ISSN 0036-8075. PMID 29242317.
  19. ^ Soloveichik, David; Seelig, Georg; Winfree, Erik (23. März 2010). "DNA als universelles Substrat für die chemische Kinetik". Verfahren der National Academy of Sciences. 107 (12): 5393–5398. Bibcode:2010pnas..107.5393s. doi:10.1073/pnas.0909380107. ISSN 0027-8424. PMC 2851759. PMID 20203007.
  20. ^ Shapiro, ehud (7. Dezember 1999). "Eine mechanische Turing -Maschine: Blaupause für einen biomolekularen Computer". Schnittstellenfokus. Weizmann Institute of Science. 2 (4): 497–503. doi:10.1098/rsfs.2011.0118. PMC 3363030. PMID 22649583. Archiviert von das Original Am 3. Januar 2009. Abgerufen 13. August 2009.

Weitere Lektüre

Externe Links