Kann eine Sprache Turing vollständig, aber unvollständig auf andere Weise?

StackOverflow https://stackoverflow.com/questions/813657

Frage

Zum Beispiel gibt es bestimmte Dinge, wenn ein Betriebssystem zu schreiben, die nicht in einer Turing kompletten Sprache erreicht werden können?

War es hilfreich?

Lösung

Nein. oder zumindest wenn man eine gefunden, die eine Widerlegung der Church-Turing-These wären .

Allerdings gibt es Sprachen, die vollständig Turing aber, in dem es eine komplette Nervensäge bestimmte Programme zu schreiben, das heißt, String-Verarbeitung in Fortran, numerische Programmierung in COBOL, Integer-Arithmetik in sed, praktisch alles in x86-Assembler .

Und dann gibt es natürlich noch Gehirnfick .

Andere Tipps

Ja, können Sie eine Sprache, die Ihnen nicht erlauben, die Hardware direkt zu manipulieren. Es wäre schwierig, ein Betriebssystem mit dem Bourne-Shell, zum Beispiel zu schreiben. Aber diese Einschränkungen sind weniger als Sie denken. Betriebssysteme sind in Standard ML geschrieben worden, Schema und sogar Haskell !

Turing-complete ist allgemeinste formale Definition der Vollständigkeit. Es gibt Sprachfunktionen, die für bestimmte Anwendungen notwendig sind, aber diese passen nicht in die formalen Definitionen.

Zum Beispiel Grafik-Fähigkeiten, die Fähigkeit, Hintergrundprozesse, um zu laichen, die Fähigkeit Zustand zu verharren, und die Fähigkeit, das Netzwerk sind alle nützlichen Funktionen zu verbinden, sondern beziehen sich nicht auf eine Turing-Vollständigkeit der Sprache. So Python auf Google App Engine oder einem Java-Applet in einer Sandbox ausgeführt ist noch Turing-vollständig.

Sie werden feststellen, dass in vielen Fällen sind diese Arten von Funktionen von Bibliotheken zur Verfügung gestellt werden, anstatt die Kernsprache.

Wenn Sie Pragmatik sind gesprochen, dann sicherlich ... können Sie eine Programmiersprache ohne die Möglichkeit vorstellen, Dateien zu lesen oder schreiben (zB eine Sprache, die jede Funktion auf ganze Zahlen berechnen kann, aber das ist es) ... Nur weil eine Sprache nicht mein Toaster bedeutet funktioniert nicht, es ist nicht Turing-vollständig, aber es bedeutet, es gibt Dinge, die es nicht tun, so dass ich bin nicht sicher, wie ‚wichtig‘ oder nützlich ist diese Unterscheidung .

Je nach Kontext, „etwas in einer Sprache erreichen“ bedeutet verschiedene Dinge für verschiedene Menschen. Turing ist einer jener Menschen, und er definiert sehr genau, was er unter „vollständig“.

Wenn eine Sprache (oder eine theoretische Maschine) Turing abgeschlossen ist, gibt es keine Turing-Berechnungen kann es nicht tun. Dies bedeutet nicht, dass die Sprache allmächtig ist, nur, dass es bei Summen gut ist. Es gibt viele „Dinge“, die nicht Turing Berechnungen, und die daher eine Turing-complete Der Computer ist möglicherweise nicht in der Lage sein.

„werden, um ein Betriebssystem“ ist keine Turing Berechnung. Um ein Betriebssystem zu sein, müssen Sie nicht nur Berechnungen mehr Dinge tun. Sie müssen auch Hardware manipulieren.

eine Turing komplette Sprache, zusammen mit einer Reihe von Operationen, bei all der Hardware-Manipulation zu tun, die Sie benötigen, einschließlich einem geeigneten Konzept der Eingabe und der Zeit, können Sie ein Betriebssystem schreiben. Oder soll ich sagen, es möglich ist, ein Betriebssystem zu schreiben. Egal, ob Sie persönlich tun können, es hängt davon ab, wie einfach die Sprache ist, mit zu arbeiten, und auf körperliche Einschränkungen, die die Turing-Definition, wie etwa, ob das resultierende Programm ignoriert würde tatsächlich passen und in dem Speicher des Geräts, das Sie ausführen möchten, um es zu betreiben, und in einer realistischen Zeit.

Das Ignorieren praktische Einschränkungen aber - ja, Sie ein Betriebssystem in jedem Turing komplette Sprache schreiben können, vorausgesetzt, dass die Sprache auch ausreichend Operationen hat die Hardware zu fahren. „Bibliothek ruft“, wenn Sie den praktischen CS Ansatz zur Unterscheidung von Sprache aus Bibliotheken in Anspruch nehmen mögen. Turing machte keine solche Unterscheidung, weil sein Rechenmodell ohnehin einen „Anruf“ das Konzept der nicht hat. Sie müssen auch das Bootstrap-Problem lösen - entweder Ihre Hardware direkt die Sprache ausführen müssen Sie schreiben, sonst müssen Sie einen Compiler in eine Sprache, die die Hardware ausgeführt wird, sonst brauchen Sie einen Dolmetscher in einer Sprache geschrieben, die die Hardware läuft. Wieder Turing ignoriert das alles, weil sein Rechenmodell abstrakte Hardware verwendet, während ein Betriebssystem zu schreiben alle über die Hardware ist.

In Englisch (statt CompSciSpeak) ist es üblich, zu sagen, dass eine Sprache „fehlt bestimmte Funktionen“, und wohl auch, dass es deshalb „nicht vollständig“ durch den Vergleich mit einer anderen Sprache, die sie hat. Man könnte Konter argumentieren, dass es möglich ist, Verschlüsse in C. Man kann implementieren zum Beispiel eines C-Programm schreiben, das ein Lisp-Interpreter ist, und darin ein Lisp-Programm als String einbetten. Voila, Verschlüsse in C. Dies ist jedoch nicht das, was die meisten Leute fragen, ob sie sagen: „Ich wünschte, C Verschlüsse hatte“. Wenn Sie jede Sprache muss Schließungen denken, dann ist C unvollständig. Wenn Sie jede Sprache muss strukturierte Programmierung denken, dann ARM-Assembler unvollständig ist. Wenn Sie denken, soll es möglich sein, Methoden zu einem Objekt dynamisch hinzufügen, dann C ++ ist unvollständig, obwohl es durchaus möglich ist, eine C ++ Klasse mit „AddMethod“ und „CallMethodByName“ Methoden und fälschen Sie Ihre eigene Methode Aufrufkonvention von dort zu schreiben. Und so weiter.

Turing glaubt nicht, Sprachen jeder dieser Komfort brauchen: sie beeinflussen nicht, was Berechnungen durchgeführt werden können, wie einfach es ist, bestimmte Programme zu schreiben. Das Konzept der Turing Vollständigkeit hat nichts zu sagen, welche Programme aussehen, oder wie sie organisiert, nur , was sie ausgegeben. Also diese Sprachen sind Turing vollständig, aber vom Standpunkt des Programmierers Sicht gibt es bestimmte Dinge, die nicht in dieser Sprache durchgeführt werden können.

Sprache kann oder kann nicht Dinge tun, wie - Subroutinen, Rekursion, benutzerdefinierte Datentypen, Schleifen, Definition von Klassen, gehe usw. Set solcher Sprachfunktionen macht es vollständig oder nicht. Zum Beispiel die Sprache unvollständig ist, wenn Sie keine Loops, gotos und Subroutinen haben - Sie alle zyklischen Betrieb nicht durchführen können. Sprache Vollständigkeit ist sehr theoretische und wissenschaftliche Sache. Wie zum Beispiel, ist es bewiesen, als auch dann, wenn Sie die Sprache nicht erlaubt rekursiv Funktionen aufrufen, sondern ermöglicht Funktionszeiger - Sie Rekursion, das heißt mit y-combinator simulieren

.

Stuff wie sehr oft mit Dateien und Hardware arbeitet, ist nicht Teil der Sprache. Um das zu erreichen Aufgabe jeder Programmierung Sie mehr als Sprache benötigen. Sie benötigen Umwelt Ihr Programm funktioniert in. In x86 als Sprache Instruktion „int“ mit einzelnen Parameter haben, aber es ist bis zu OS bestimmte Operationen auszuführen, wenn Sie „int 21h“ aus.

Sprache braucht nur etwas Art und Weise mit der Umgebung zu kommunizieren und vollständig sein - dann ist es an Umwelt mit ihm zu arbeiten. Es ist gültig in x86 asm „mov ax, bx“ zu schreiben, aber es ist bis zu Ihrer CPU diesen Vorgang auszuführen.

Als unvollständig auf andere Weise - einfach nur Ihre eigene Version der Vollständigkeit definieren. das heißt ich hasse ohne klassenbasierte OOP zu arbeiten, so definieren wir, dass die Sprache nicht Feldman-vollständig ist, wenn sie nicht über die Sprache verfügt unterstützt klassenbasierten OOP. Ok dann, C und Javascript ist nicht F-vollständig. Sie können immer noch alles in diesen Sprachen tun, und auch klassenbasierten OOP bis zu einem gewissen Niveau simulieren.

In Bezug auf OS - Sie noch Prozessor benötigen, die Anweisungen und Compiler ausgeführt wird, die Sprache in CPU-Befehle übersetzt. Ich kann Compiler übersetzen, etwas zu Maschinen-Codes vorstellen. Wie, gelten folgende JS-Code 

for(var i=0;i<10;i++){
 mov("ax",i);
 int(0x21);
}

und es sollte nicht so schwer sein, sie in den Maschinencode zu kompilieren.

In der modernen Welt, die Sie nicht nur die Sprache wählen, wählen Sie auch Plattform, Standard- und Nicht-Standard-Bibliotheken, Literatur, Gemeinschaft, Unterstützung, usw. All diese Dinge beeinflussen Ihre Fähigkeit, bestimmte Sache zu tun, und sie ganz ergriffen werden können oder kann nicht „vollständig genug“ für Ihre Aufgabe. Aber wenn ich nicht c ++ Code kompilieren Java-Applet, das bedeutet nicht, es ist eine C ++ Sprache Unvollständigkeit. Es ist nur Abwesenheit von Compiler, c ++ Code zu etwas verwandeln, die von JVM geladen werden kann.

Wenn Sie möchten, können Sie eine Sprache mit Sprachfunktionen Design wie „Openfile, PingNetworkHost, DownloadMpeg4FileOverHttpsAndPlayBackwards“. Aber wenn die Sprache sie nicht haben, können sie immer noch mit anderen Sprachfunktionen und Umwelt Unterstützung implementiert werden, so Fehlen solcher Merkmale nicht die Sprache unvollständig machen. Wenn Ihre Sprache wie C, aber ohne goto Operator, Loop Operator (, während tun, während) und Funktionen, dann können Sie nicht zyklisches Programm schreiben und keine Umgebung und Bibliotheken können Ihnen helfen.

Die Antwort ist ein sehr klares Ja. Turing Vollständigkeit bedeutet nur, dass eine Turing komplette Sprache verwendet wird, kann jede berechenbare Funktion zu berechnen. Zum einen sagt es nichts über die Komplexität einer Berechnung.

Sie können in der Regel erwarten, dass jeder Polynomialzeitalgorithmus kann als Polynomialzeitalgorithmus in jeder anderen Turing komplette Sprache ausgedrückt werden, aber das ist es. Vor allem keine Echtzeitanforderungen (weich oder hart) gehen aus dem Fenster, wenn Ihr nur Fokus Turing Vollständigkeit ist.

Eine weitere wichtige Sache ist Ausdruckskraft einer Sprache, die weitgehend eine subjektive Eigenschaft ist, aber man kann erkennen, dass die Programme sehr viel schwieriger sind in jedem Maschinencode zu schreiben, als, sagen wir, Java.

Wie für Betriebssysteme, eine Schnittstelle zur Hardware ist ein Muss, aber jede Sprache kann mit diesen Utilities ausgestattet werden.

[Bearbeiten] Eine andere Sache, wie ich hinzufügen möchte ist, dass keine tatsächliche Implementierung einer beliebigen Programmiersprache ist Turing vollständig von der Natur unserer endlichen Rechenmaschinen. Während die Kirche-Turing-These, zusammen mit verwandten Samen Entdeckungen (wie das Halteproblem), eine Grundlage für unser Verständnis des Computing legen, aber nur selten in der Welt des praktischen Computing erfüllen.

Unvollständige Verwendbarkeit:)

Wenn die Rede von Sprachen ist, wird angenommen, in der Regel, dass die Sprachen auf einigen sehr einfachen Maschinen laufen. Als solches Konzept jeder aus einer Datei lesen oder Zugriff auf das Netzwerk in Bezug betrachtet wird normalerweise nicht auf die Kraft der Sprache.

Es gibt verschiedene Klassen von Sprachen, die oft in Berechenbarkeit Theorie verwendet werden (jeder mit fast endlosen Änderungen)

  1. endliche Automaten. Dies ist die einfachste Klasse von Maschinen und sie können die kleinste Klasse von Sprachen erkennen, die die um genau zu sein geschieht Sprachen, die regulären Ausdrücke erkennen können, dh. ob eine Zeichenfolge mit zwei ‚a den beginnt und mit d beenden. Sie können nicht erkennen, verwendet werden, ob eine Zeichenfolge eine ausgewogene Gruppe von Klammern enthält, fx.
  2. nach unten drücken Automaten. Dies ist im Wesentlichen eine Erweiterung des Zustandsautomaten mit einem Stapel. Im Gegensatz zu endlichen Automaten, können sie verwendet werden, zu sagen, ob eine bestimmte Zeichenfolge einen ausgewogenen Satz von Klammern enthält. Die Sprachen, die Automaten nach unten drücken erkennen kann, ist genau die das Set als beschrieben werden kann freie Grammatiken und sie werden oft verwendet, unter Verwendung von Kontext-Quellcode zu analysieren.
  3. Turingmaschinen. Dies sind die mächtigsten der Klasse von Maschinen hier, aber das bedeutet nicht, dass sie verwendet werden kann, um alle Fragen zu beantworten. Sie sind unfähig, die Frage zu beantworten, ist diese Zeichenfolge eine Turing-Maschine beschreiben, die immer laufen wird? In der Tat kann jeder einer Turing-Maschine nichts sagt über die nicht-trivialen Eigenschaften einer Turing-Maschine (Reis Satz).

Also ja eine Turing-Maschine hat ihre Grenzen, und es gibt Klassen von Maschinen, die etwas eine Turing-Maschine kann tun können, nicht, aber sie haben (alles wird aller Wahrscheinlichkeit nach) immer nur in der Theorie existiert, neuere in der Praxis.

Ich glaube nicht, Definitionen der Vollständigkeit anders als Turing (oder reguläre Ausdrücke oder Push-down-Automaten) relevant sind für Sprachen . Aber dieser Vollständigkeit ist nur in Bezug auf die numerischen oder symbolischen Rechenanlagen.

Die Dinge, die Sie erwähnen, scheinen mir mehr zu sein, eine Funktion der Laufzeit und Umwelt als die Sprache. Es ist eine wichtige Unterscheidung, und formale Begriffe Vollständigkeit der Regel nur auf Sprachen selbst gelten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top