Ich weiß ein bisschen was ein ist Turing Maschine und ein Komplettierung Sprache, aber um es besser zu verstehen, könnte jemand Beispiele für Sprachen geben, die nicht vollständig Turing sind? (Vielleicht auch Maschinen, die nicht Turing sind?)
Antworten:
12 für die Antwort № 1Reguläre Ausdrücke in der formalen Definition, bestehend nur aus:
- Verkettung (ab)
- unbegrenzte Wiederholung (a *)
- Wechsel (a | b)
- Gruppierung ((ab) | (cd))
kann nur reguläre Sprachen erkennen. Eine Turing-komplette Programmiersprache kann rekursiv aufzählbare Sprachen erkennen.
Ein Beispiel ist, dass reguläre Ausdrücke Ihnen nicht sagen können, ob eine Zeichenfolge aus übereinstimmenden Klammerpaaren besteht: z ()(()) wird während akzeptiert ()((())() wird abgelehnt, während Turing-komplette Programmiersprachen können.
(Beachten Sie, dass Ausdrücke in modernen Programmiersprachen leistungsfähiger sind als die formale akademische Definition von regulären Ausdrücken. Einige können sogar vollständig sein.)
3 für die Antwort № 2
Reguläre Sprachen - diejenigen, die als reguläre Ausdrücke bezeichnet werden können - sind Turing nicht abgeschlossen.
Markup-Sprachen (zur Beschreibung von Daten, nicht zum Berechnen) wie XML und JSON sind nicht vollständig.