Kernpunkte und Bedeutung der Entscheidbarkeit

Question

Eine Sprache ist entscheidbar Wenn ein TM die Sprache erkennt und geht in einen Zustand annehmen oder ablehnen. Als Entwickler. Ich denke, das ist wichtig, da es bedeuten würde, wir, wenn ein Programm Pufferüberlauf oder Deadlocks enthält bestimmen könnten. Auch sind die folgenden Probleme Un-Entscheidbare:

• Ist ein Programm, das jemals eine nicht initialisierte Variable zuzugreifen.
• Do zwei kontextfreie Grammatiken beschreiben das gleiche Langauge.
• Macht es einen Unterschied, ob Parameter an ein Unterprogramm als Referenz übergeben werden oder durch copy-Ergebnis

Im Hinblick auf die Entscheidbarkeit was würden Sie die wichtigsten Punkte zu Entscheidbarkeit sagen sind und warum ist Entscheidbarkeit wichtig (insbesondere ein Entwickler).

Hinweis: Aufzählungszeichen sind in Ordnung in Antworten - ich mir die Themen nachschlagen kann. Ich will nur wissen, was die wichtigsten Punkte sind.

Answer 1

Vielleicht gehört dies in dem cstheory Austausch , aber ich werde auf jeden Fall geht an ihn hat.

Der entscheidende Punkt ist: Einige Probleme sind unentscheidbar, das heißt nicht lösbar durch einen Algorithmus, so sollten sie mit anderen Methoden in Angriff genommen werden. Unter diesen Problemen viele „Meta-Probleme“ betreffend sind Computersprachen, zum Beispiel das Problem der ein Virus zu erkennen.

Nachdem bestimmt wurde, dass ein Problem unentscheidbar ist, gibt es mehrere mögliche Handlungsoptionen:

1. kann einige Probleme halb entscheidbar, das heißt, es ist ein halb -Algorithmus, dass löst einige Fälle, aber Schleifen für immer auf den anderen Fällen. Wenn ein halbAlgorithmus implementiert, setzen Sie einen Timer auf sie und Rückkehr no answer, wenn die Zeit abgelaufen ist.
2. Lösen Sie nur ein paar, hoffentlich entscheidende Teile des Problems, indem sie es vereinfacht wird.
3. 2 + den Benutzer zur Eingabe fragen, wann das Problem zu komplex wird.
4. Verwenden Sie eine Heuristik, die die richtige Antwort bekommt die meisten der Zeit.
5. Verwenden Sie eine andere Sprache, vielleicht ein nicht-Turing vollständig ein.

1 bis 3 sind sehr beliebt für die automatisierte Argumentation Tools, einschließlich Programm Gutachter. 4 ist das, was Virenscanner tun. 5 ist eine gute Wahl , wenn Benutzer zu schreiben Scripts ermöglicht ein größeres System zu automatisieren ; anstatt sie voll JavaScript / Schema / Lua geben / was auch immer, geben ihnen eine eingeschränkte Teilmenge, die nicht unbegrenzt Rekursion / Schleifen erlaubt.

Answer 2

Angenommen, Sie einige Software zu schreiben, dass die Bedingung erfüllt. „Zur Laufzeit wird keine Funktion jemals selbst direkt am Ende Aufruf oder indirekt“

Diese Bedingung wäre unentscheidbar, aber eine einschränkende Bedingung entscheidbar sein kann, zum Beispiel so etwas wie: „keine Funktionszeiger verwendet werden soll und keine Funktion werden Anrufe selbst direkt oder indirekt enthalten“

Das zu Highlight ist, dass manchmal ist es möglich, den Handel Flexibilität für decidability, so dass bestimmte erforderliche Eigenschaften des Systems vollstreckbar können.

Wenn eine Programmiersprache entscheidbar ist, dann wird es immer möglich sein, zu entscheiden, ob ein Programm ein gültiges Programm für diese Sprache oder nicht.

Aber selbst wenn ein Programm ein gültiges Programm für diese Sprache ist, bleibt unentscheidbar, ob das Programm einen Pufferüberlauf oder ein Deadlock entstehen.