Skip to content
TheChatArchiveThe Chat Archive
Human-written demonstration (OpenAssistant volunteers)· OpenAssistant (human-written)Hugging Face OpenAssistant Conversations (oasst2)

Sind Regular Expressions Turing Complete? Falls dies nicht der Fall ist erkläre mir…

In OpenAssistant data, “assistant” turns were written by human volunteers as demonstrations. They are not model outputs.
  1. User

    Sind Regular Expressions Turing Complete? Falls dies nicht der Fall ist erkläre mir wieso sie es nicht sind?

  2. Assistant

    Ursprünglich wurden Reguläre Ausdrücke benutzt, um reguläre Sprachen zu beschreiben, die nicht Turing-vollständig sind. Heute bezeichnet "Regulärer Ausdruck" jedoch eine Vielzahl von Mustererkennungsprogrammen, die zum Teil Turing-Vollständigkeit besitzen. Zur Überprüfung ob ein bestimmtes Mustererkennungsprogramm Turing-vollständig ist, empfiehlt es sich dieses als Sprach-Generator zu betrachten, im speziellen als Instanzen des Markov Algorithmus.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.