Sind regelmäßige Ausdrücke Turing Complete? Wenn dies nicht der Fall ist, erklären Sie mir, warum sie nicht sind?
Regelmäßige Ausdrücke sind nicht Turing-komplett. Dies ist, weil reguläre Ausdrücke in Deterministische Final Automata (DFAs) umgewandelt werden können und DFAs die Buchstaben eines Eingabestrings auf dem Weg zwischen zwei Zuständen verbraucht werden und nie wieder abgerufen werden können. Einige wichtige Aspekte einer Turing-Maschine sind, dass sie sich vorwärts und zurück bewegen und auf Teile der bereits besuchten Eingangskette zugreifen können. Sie können Symbole aufschreiben, die einer „Speicherung" gleichwertig sind. Alles, was ein DFA tun kann, kann auch eine Turing-Maschine sein. Aber eine Turing-Maschine kann ihre zusätzlichen Fähigkeiten nutzen, um viel anspruchsvollere Sprachen als ein DFA zu bestimmen, so dass DFAs nicht Turing-komplett sind.