Berechenbarkeit

Alphabet
Symbol
Wort
Länge eines Wortes/leeres Wort
$\Sigma ^i$
$\Sigma ^*$
lexikographische Ordnung
quasi-lexikographische Aufzählung
$\Sigma ^+$
formale Sprache
Wortfunktion
Entscheidungsproblem
Wortproblem
deterministische Turingmaschine
Befehl
Konfiguration
Anfangskonfiguration
Endkonfiguration
Folgekonfiguration
Berechnung
unendliche Berechnung
Bandinhalt
erfolgreiche Berechnung
durch eine DTM berechnete Funktion
T-berechenbare Funktion
DTM Variationen
Registermaschine
Registermaschinenprogramm
elementare Befehle RM
Konfiguration RM
Endkonfiguration RM
Anfangskonfiguration RM
Folgekonfiguration RM
erfolgreiche Berechnung RM
durch RM berechnete Funktion
R-berechenbare Funktion
TM vs. RM
Church'sche These
Algorithmus
berechenbare Funktion (allgemein)
Nachweis Berechenbarkeit
Anzahl berechenbarer Funktionen
Entscheidbarkeit
Entscheidbarkeit Komplement
Entscheidbarkeit $\cup / \cap$
Reduzierbarkeit
Folgerung Reduzierbarkeit
Gödelisierung (allgemein)
Gödelisierung einer Turing-Maschine
Gödelisierung eines Zustandsübergang
Zuordnung Wort zu TM
spezielles Halteproblem
allgemeines Halteproblem
Halteproblem auf leerem Band
Satz von Rice
Korrektheitsproblem
Post'sches Korrespondenzproblem
Satz von Post
Satz von Church-Turing
Semi-Entscheidbarkeit
alternative Def. Semi-Entscheidbarkeit
Semi-Entscheidbarkeit $\cup /\cap$
Semi-Entscheidbarkeit Komplement
Semi-Entscheidbarkeit Reduzierbarkeit
$A$ und $\overline{A}$ aufzählbar

Kommentare

Nur angemeldete Nutzer dürfen kommentieren. Hier geht's zur kostenlosen Registrierung.