Was ist Turing-Vollständig?

https://stackoverflow.com/questions/7284

08-06-2019
|

Frage

Was bedeutet der Ausdruck "Turing-Vollständig" bedeuten?

Können Sie geben eine einfache Erklärung, ohne in zu vielen theoretischen details?

Lösung

Hier die kürzeste Erklärung:

Ein Turing-Vollständiges system ein system, in dem ein Programm geschrieben werden kann, der wird eine Antwort finden (obwohl mit keinerlei Garantien in Bezug auf Laufzeit-oder Speicher).

Also, wenn jemand sagt: "meine neue Sache ist Turing-Vollständig", das heißt im Prinzip (wenn auch oft nicht in der Praxis) könnte verwendet werden zu lösen jede Berechnung problem.

Irgendwann ist es ist ein Witz...ein Mann schrieb eine Turing-Maschine-simulator in vi, so es ist möglich zu sagen, dass vi ist der einzige computational engine, die jemals benötigt in der Welt.

Andere Tipps

Hier ist die einfachste Erklärung

Alan Turing schuf eine Maschine, ein Programm, und führen Sie das Programm und zeigen Ergebnis.Aber dann hatte er die zum erstellen von verschiedenen Maschinen für verschiedene Programme.So schuf er die "Universelle Turing Maschine", können JEDES Programm und führen Sie es.

Programmiersprachen sind ähnlich denen Maschinen (obwohl virtuelle).Nehmen Sie Programme und führen diese aus.Nun, eine Programmiersprache wird als "Turing-complete", wenn Sie, dass es kann ein Programm ausführen(unabhängig von der Sprache), die eine Turing-Maschine ausführen können, wenn Sie genügend Zeit und Speicher.

Zum Beispiel:Sagen wir, es ist ein Programm, das dauert 10 zahlen und fügt Sie hinzu.Turing-Maschine kann leicht führen Sie dieses Programm aus.Aber nun Stell dir vor aus irgendeinem Grund Ihre Programmiersprache nicht tun können, die gleiche hinaus, dann ist es Turing-Maschine unvollständig.Auf der anderen Seite, wenn Sie ein Programm ausführen wie die Universelle turing-Maschine ausführen können, dann ist es Turing-vollständig.

Die meisten modernen Programmiersprachen wie Java, JavaScript, Perl, etc sind alle turing-vollständig, da Sie alle realisieren alle die Funktionen erforderlich, um Programme ausführen, wie addition, Multiplikation, if-else-Bedingung, return-Anweisungen, Möglichkeiten zum speichern/abrufen/löschen von Daten und so weiter.

Update:Sie können lernen, mehr auf my blog post: "JavaScript Ist Turing-Vollständig", — Erklärte

Von wikipedia:

Turing-Vollständigkeit, benannt nach Alan Turing, wesentlich ist, dass jeder plausibel-design für eine computing Gerät so weit nachgebildet werden kann durch eine Universelle Turing-Maschine — eine die Beobachtung, dass bekannt geworden als die Church-Turing-these.So eine Maschine, die können handeln als eine Universelle Turing-Maschine kann, im Prinzip, führen Sie eine Berechnung, die andere programmierbare computer in der Lage ist.Aber das hat nichts zu tun mit der Aufwand, ein Programm zu schreiben für die Maschine, die Zeit, die es dauern kann für die Maschine zu führen Berechnung, oder irgendwelche Fähigkeiten, die Maschine besitzen kann, die in keiner Beziehung zu Berechnung.

Während wirklich Turing-vollständigen Maschinen sehr wahrscheinlich ist physikalisch unmöglich, als Sie erfordern, unbegrenzten Speicher Turing-Vollständigkeit ist oft Locker zurückzuführen auf physikalische Maschinen oder Programmiersprachen, die sein würde universal, wenn Sie hatte unbegrenzte storage.Alle modernen Computer sind Turing-vollständige, in diesem Sinne.

Ich weiß nicht, wie Sie können werden mehr nicht-technische, als dass, außer mit den Worten: "den turing bedeutet" in der Lage zu beantworten berechenbare problem genügend Zeit und Raum'".

Informelle Definition

Eine Turing-vollständige Sprache ist eine, die kann führen Sie eine Berechnung aus.Die Church-Turing-These besagt, dass jeder performable Berechnung kann durch eine Turing-Maschine.Ein Turing-Maschine ist eine Maschine mit unendlicher random access memory und einer endlichen 'Programm', das bestimmt, Wann sollte es Lesen, schreiben und bewegen sich über das Gedächtnis, wenn es beendet werden soll mit einem bestimmten Ergebnis, und was er als Nächstes tun sollte.Die Eingabe einer Turing-Maschine ist in seinem Gedächtnis, bevor es beginnt.

Dinge, die eine Sprache NICHT Turing-vollständige

Eine Turing-Maschine kann machen Entscheidungen basierend auf dem, was es sieht im Speicher - Die 'Sprache', die nur unterstützt +, -, *, und / auf ganzen zahlen ist nicht Turing-vollständig, da es nicht eine Wahl treffen, basierend auf seinem Eingang, aber eine Turing-Maschine kann.

Eine Turing-Maschine ausführen können, für immer - Wenn wir Java, Javascript oder Python und entfernt die Fähigkeit zu tun, jede Art von loop -, GOTO -, oder-Funktion nennen, wäre es nicht Turing-vollständig, da es nicht ausführen kann eine beliebige Berechnung, die nie endet. Coq ist ein theorembeweiser, dass kann nicht express-Programme, die nicht terminieren, so es ist nicht Turing-vollständig.

Eine Turing-Maschine kann unendlich Speicher - Eine Sprache, die war genau wie Java, aber würde kündigen, sobald es mehr als 4 Gigabyte Speicher wäre nicht Turing-vollständig, da eine Turing-Maschine kann unendlich Speicher.Dies ist, warum können wir eigentlich nicht bauen eine Turing-Maschine, aber Java ist immer noch eine Turing-vollständige Sprache, weil die Java - Sprache hat keine Beschränkung, verhindern, dass es mit unendlichen Speicher.Dies ist ein Grund, reguläre Ausdrücke sind nicht Turing-vollständig.

Eine Turing-Maschine hat random access memory - Eine Sprache, die nur können arbeiten Sie mit Speicher durch push und pop Operationen, um einen Stapel wäre nicht Turing-vollständig.Wenn ich eine 'Sprache', das liest einen string einmal und können nur Speicher durch drücken und knallen von einem Stapel, Sie können mir sagen, ob alle ( in der string hat seine eigene ) später auf, indem Sie drücken, wenn es sieht ( und Tauchen auf, wenn es erkennt ).Es kann jedoch nicht sagen, wenn mich jeder ( hat seine eigenen ) später und jeder [ hat seine eigenen ] später (beachten Sie, dass ([)] ist dieses Kriterium erfüllt, aber ([]] nicht).Eine Turing-Maschine kann mit Ihren Arbeitsspeicher zu verfolgen ()'s und []'s getrennt, aber diese Sprache mit nur einem Stapel nicht.

Eine Turing-Maschine simulieren kann jede andere Turing-Maschine - Eine Turing-Maschine, wenn ihm eine entsprechende "Programm", kann nehmen eine andere Turing-Maschine 'Programm' und simulieren Sie auf beliebigen Eingang.Wenn Sie hatten eine Sprache, die verboten war, sich von der Umsetzung ein Python-interpreter, wäre es nicht Turing-vollständig.

Beispiele von Turing-vollständige Sprachen

Wenn Ihre Sprache hat eine unendliche random access memory, bedingte Ausführung, und irgendeine form von wiederholten Ausführung, ist es wahrscheinlich Turing-vollständig.Es gibt mehr exotische Systeme, die doch noch erreichen kann alles, was eine Turing-Maschine kann, das macht Sie Turing-vollständig zu sein:

Untypisierte lambda-Kalkül
Conway ' s Spiel des Lebens
C++ - Vorlagen
Prolog

Grundsätzlich Turing-Vollständigkeit ist eine präzise Anforderung, unbounded recursion.

Auch nicht begrenzt durch Speicher.

Ich dachte, dies unabhängig voneinander, aber hier ist eine Diskussion der Behauptung. Meine definition von LSP sorgt für mehr Kontext.

Die anderen Antworten hier nicht direkt definieren die grundlegende Essenz der Turing-Vollständigkeit.

Turing-Vollständig bedeutet, dass es ist mindestens so mächtig wie eine Turing-Maschine.Dies bedeutet, dass alles, was berechnet werden kann durch eine Turing-Maschine berechnet werden kann durch eine Turing-Complete-system.

Niemand hat noch ein system gefunden, das stärker als eine Turing-Maschine.So, für den Augenblick, zu sagen, ein system ist Turing-Vollständig ist das gleiche wie zu sagen, das system ist so mächtig, wie alle bekannten computing system (siehe Church-Turing-These).

In der einfachsten Form, eine Turing-complete-system können lösen jede möglich computational problem.

Eine der wichtigsten Voraussetzungen ist die scratchpad-Größe sein, unbegrenzt und kann Zurückspulen, um den Zugriff vor schreibt, um das Eingabefeld zu.

So wird in der Praxis kein system ist Turing-vollständig.

Eher einige Systeme Ungefähre Turing-Vollständigkeit durch die Modellierung von unbegrenzten Speicher und darstellende mögliche Berechnung, die können fit in memory.

Ich denke, die Bedeutung des Begriffs der "Turing-Vollständig" ist, in der die Fähigkeit zum erkennen einer Rechenmaschine (nicht unbedingt eine mechanische/elektrische / "computer"), der kann seine Prozesse zerlegt werden in "einfache" Anweisungen aus einfacher und einfacher Anweisungen, die eine Universelle Maschine interpretieren könnte und dann ausführen.

Ich empfehle Das Kommentierte Turing

@Mark ich denke, was Sie erklären, ist eine Mischung zwischen der Beschreibung der Universellen Turing-Maschine und Turing-Vollständig.

Etwas, das den Turing, im praktischen Sinne, wäre eine Maschine/ - Prozess/ - Berechnung können werden geschrieben und dargestellt, wie ein Programm ausgeführt werden kann, indem Sie einen Universal-Rechner (desktop-computer).Obwohl es nicht nehmen Berücksichtigung der Zeit oder der Lagerung, wie von anderen erwähnt.

Was ich verstehen in einfachen Worten:

Turing : Eine Programmiersprache / - Programm, das die Berechnung ist Turing-vollständig.

Zum Beispiel :

Können Sie fügen Sie zwei zahlen mit Nur HTML.(Ans ist"Keine'Sie haben javascript ausführen Zusatz.), Daher HTML ist nicht Turing-Vollständig.
Sprachen wie Java , C++, Python, Javascript, Solidität für Astraleums etc sind Turing-Vollständig, da Sie die Berechnung wie das hinzufügen von zwei zahlen mit Hilfe dieser Sprachen.

Hoffe, das hilft.

Als Waylon sagte Flinn:

Turing-Vollständig bedeutet, dass es ist mindestens so mächtig wie eine Turing-Maschine.

Ich glaube, dass dies falsch ist, wird eine system ist Turing-vollständig, wenn es genau so mächtig wie die Turing-Maschine, d.h.alle Berechnungen durchgeführt, die von der Maschine getan werden kann, indem das system, sondern auch jede Berechnung durchgeführt, indem das system kann getan werden, indem die Turing-Maschine.

In der praktischen Sprache, Begriffen die meisten Programmierer vertraut, den gewohnten Weg zu erkennen Turing-Vollständigkeit ist, wenn die Sprache erlaubt oder ermöglicht die simulation von verschachtelten unbegrenzt, während Aussagen (im Gegensatz zu Pascal-Stil für Aussagen, mit festen Obergrenze).

Kann eine relationale Datenbank, Eingabe -, breiten-und Längengrade von Orten und Straßen, und berechnen Sie den kürzesten Pfad zwischen Ihnen - nicht.Dies ist ein problem, das zeigt, SQL ist nicht Turing-vollständig.

Aber C++ kann es tun, und tun können, jedes problem.So ist es.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow