Ich weiß ein wenig darüber, was turing-machine und turing-complete Sprache, aber zu verstehen Besser, könnte jemand Beispiele für Sprachen nennen, die nicht vollständig Turing sind? (Vielleicht sogar Maschinen, die nicht Turing sind?)
Reguläre Ausdrücke in der formalen Definition, bestehend nur aus:
kann nur reguläre Sprachen erkennen. Eine Turing-vollständige Programmiersprache kann rekursiv aufzählbare Sprachen erkennen.
Ein Beispiel ist, dass reguläre Ausdrücke Ihnen nicht sagen können, ob eine Zeichenfolge aus zusammengehörenden Paaren von Klammern besteht: zB ()(()) wird akzeptiert, während ()((())() abgelehnt wird, während Turing-vollständige Programmiersprachen können.
(Beachten Sie, dass Regexes in modernen Programmiersprachen mächtiger sind als die formale akademische Definition von regulären Ausdrücken. Manche sind sogar Turing-vollständig.)
Reguläre Sprachen - diejenigen, die als reguläre Ausdrücke beschrieben werden können - sind nicht Turing abgeschlossen .
Markup-Sprachen (zur Beschreibung von Daten, nicht zur Berechnung) wie XML und JSON sind nicht vollständig Turing.
Tags und Links computer-science turing-machines turing-complete