Berechenbarkeitstheorie
- Negation der Pumpingeigenschaft
- Turingreduktion
- Satz Turingreduktion ist transitiv
- Satz Turingreduktion ist reflexiv
- Berechenbarkeitstheorie
- Folgerungsbeziehungsproblem der Prädikatenlogik
- Erfüllbarkeitsproblem der Prädikatenlogik
- Erfüllbarkeitsproblem der Aussagenlogik
- Satz Halteproblem für Turingmaschinen ist unentscheidbar
- Universale Sprache
- nicht-triviale semantische Eigenschaft
- Satz von Friedberg und Muchnik
- Polynomialzeitreduktion
- Log-Raum-Reduktion
- Satz Auf entscheidbare Sprache Turing-reduzierbare Sprache ist entscheidbar
- Reduktion
- Satz Jede Sprache ist Turing-reduzierbar zu ihrem Komplement
- Satz Jede Sprache ist einseitig Turing-reduzierbar zu ihrem Jump
- Jump
- Satz Allgemeine Wortproblem für Turingmaschinen ist unentscheidbar
- Allgemeines Wortproblem für Turingmaschinen
- Satz epsilon-Halteproblem für Turingmaschinen ist unentscheidbar
- epsilon-Halteproblem für Turingmaschinen
- Halteproblem für Turingmaschinen
- Halteproblem
- Satz von Rice
- Satz von Kleene und Post
- Einseitige Turingreduktion
- Pumpinglemma für Kontextfreie Sprachen
- Pumpinglemma für reguläre Sprachen
- Satz Jede reguläre Sprache wird von DKA erkannt
- Durch leeren Keller erkannte Sprache eines NDKA
- Durch Endzustand erkannte Sprache eines NDKA
- Satz durch Endzustand und durch leeren Keller erkannt ist äquivalent
- Satz NDKA von Endzustand zu äquivalenten leeren Kelller
- Satz NDKA von leeren Keller zu äquivalenten Endzustand
- Berechnung eines NDKA
- Erkannte Sprache
- Akzeptiertes Wort
- Satz ungelese Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht
- Sprache Palindrom
- Satz NEA zu regulärer Ausdruck
- Zustand aus einem GNEA entfernen
- Berechnung eines GNEA
- Berechnung eines NEA
- Nichtdeterministischer endlicher Automat
- Satz Kleene Hülle eines NEAs
- Satz Konkatenation zweier NEAs
- Satz Vereinigung zweier NEAs
- Universelle Turingmaschine
- Satz Komplement von Allgemeine Wortproblem ist nicht erkennbar
- Satz Allgemeine Wortproblem ist erkennbar
- Satz Regulärer Ausdruck zu NEA
- Satz DEA zu NEA
- epsilon-Pfad
- w-Pfad
- Satz reverse ist nicht sequentiell
- Lemma des linear beschränkten Abstandswachstum
- Lemma des linear beschränkten Längenwachstum
- Sequenzielle Funktion
- Satz raise ist nicht sequentiell
- Funktion raise
- Berechenbare Funktion
- Pumpingeigenschaft
- Erkannte Sprache eines DEA
- Berechnung eines DEA
- Berechnung
- Berechnung einer TM
- Deterministischer endlicher Automat
- Partielle Funktion
- Satz Redundanz zusätzlicher Bänder
- Nur-Lesen Eingabeband Turingmaschine
- Logarithmische Platzkomplexität berechenbare Funktion
- Satz Anzahl der Konfiguration einer ROITM
- Satz Anzahl der Konfiguration einer TM
- Probabilistische Entscheidbarkeit
- Polynomialzeit berechenbare Funktion
- Äquivalenz DEA, NEA und Reg
- Turingmaschine
- Reguläre Urbildmengen
- Mehrband-Turingmaschine
- Nichtdeterministische Turingmaschine
- Deterministische Turingmaschine
- Satz Redundanz von Nichtdeterminismus