Aufhalten in nicht-Turing-complete Sprachen

Question

Das Halteproblem kann nicht für Turing komplette Sprachen gelöst werden, und es kann trivialerweise für einige Nicht-TC-Sprachen wie reguläre Ausdrücke gelöst werden, wo es immer anhält.

Ich habe mich gefragt, ob es irgendwelche Sprachen sind, die sowohl die Fähigkeit zu stoppen zu stoppen hat und nicht räumt aber ein, einen Algorithmus, der feststellen kann, ob es hält.

Answer 1

Ja. Eine wichtige Klasse dieser Art sind primitive rekursive Funktionen . Diese Klasse umfasst alle grundlegenden Dinge, die Sie mit den Zahlen (Addition, Multiplikation, etc.), sowie einige komplexe Klassen zu tun, erwarten zu können, wie @adrian (reguläre Ausdrücke / endliche Automaten, kontextfreie Grammatiken erwähnt hat / Pushdown- Automaten). Es tun gibt es jedoch Funktionen, die nicht primitiv-rekursiv sind, wie die Ackermann Funktion .

Es ist eigentlich ziemlich einfach, primitiv-rekursiven Funktionen zu verstehen. Sie sind die Funktionen, die Sie in einer Programmiersprache bekommen konnte, die keine echte Rekursion hatte (so eine Funktion f selbst nicht anrufen kann, sei es direkt oder durch eine andere Funktion g aufrufen, die dann f Anrufe, etc.) und hat keine While-Schleifen, stattdessen hat for-Schleifen begrenzt. A begrenzt for-Schleife ist eine, wie „für i von 1 bis r“, wobei R eine Variable ist, die bereits früher in dem Programm berechnet wurden; Auch kann ich nicht innerhalb der for-Schleife modifiziert werden. Der Punkt einer solchen Programmiersprache ist, dass alle Programm hält.

Die meisten Programme, die wir schreiben, sind eigentlich primitive rekursive (ich meine, kann in eine solche Sprache übersetzt werden).

Answer 2

Das Halteproblem auf Sprachen nicht handeln. Vielmehr handelt es sich bei Maschinen (Das heißt, Programme). Es fragt, ob ein bestimmtes Programm hält an einem bestimmten Eingang

Vielleicht meint man sich fragen, ob es auch für andere Modelle gelöst werden kann Berechnung (wie reguläre Ausdrücke, die Sie erwähnen, aber auch wie Automaten Push-down).

Halting kann in der Regel wird bei den Modellen mit begrenzten Ressourcen erkannt (wie Reguläre Ausdrücke oder äquivalent endliche Automaten, die ein festes haben Anzahl der Zustände und kein externer Speicher). Dies wird leicht erreicht durch Aufzählen alle möglichen Konfigurationen und Prüfen, ob die Maschine betritt die gleiche Konfiguration zweimal (eine unendliche Schleife angibt); mit endlicher Ressourcen können wir eine obere Grenze auf der Höhe der Zeit setzen, bevor wir muss sehen eine wiederholte Konfiguration, wenn die Maschine stoppt nicht.

Normalerweise Modelle mit unendlichen Ressourcen (unbegrenzt TMs und PDAs, zum Beispiel), kann nicht halt geprüft werden, aber es wäre am besten, um die Modelle zu untersuchen und ihre offenen Probleme einzeln.

(Sorry für alle Wikipedia-Links, aber es ist eigentlich eine sehr gute Quelle für diese Art von Frage.)

Answer 3

Die kurze Antwort lautet ja, und solche Sprachen können auch sehr nützlich sein.

Es gab eine Diskussion darüber vor ein paar Monaten auf LTU: http://lambda-the-ultimate.org/node/2846