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