Berechenbarkeit und Komplexität
Berechenbarkeit und Komplexität für Informatiker
Berechenbarkeit und Komplexität für Informatiker
Welche der folgenden Aussagen gilt nicht?
\(Welche\ der\ folgenden \ Aussagen \ lässt \ sich \ nach \ heutigem \ Wissenstand \ \textit{nicht} \ beantworten? \\\\ a) \ DSPACE(n^3) \subseteq NSPACE(n^5) .\\ b) \ 3-F\ddot{A}RBBARKEIT \in P.\\ c) \ 2-F\ddot{A}RBBARKEIT \in NP .\\ d) \ SAT \in PSPACE \)
c
\( Welche \ der\ folgenden\ Aussagen\ gilt\ \textit{nicht}? \\\\ a) \bigcup_{k \geq 0} NSPACE(n^k) \subseteq \bigcup_{k \geq 0} DSPACE(n^k) .\\ b) Das\ Halteproblem\ für\ Turingmaschinen\ lässt\ sich\ auf\ SAT\ reduzieren. \\ c) Jede\ Sprache\ in\ DTIME(n) \ lässt\ sich\ auf \ SAT\ reduzieren.\\ d) SAT \in PSPACE . \)
b
Sei HALBSAT das Problem, auf Eingabe einer aussagenlogischen Formel F zu entscheiden, ob eine erfüllende Belegung für F existiert, die genau die Hälfte der Variablen in F mit wahr belegt.
Sei INDEPENDENTSET das Problem, auf Eingabe eines ungerichteten Graphen und einer natürlichen Zahl k zu entscheiden, ob es eine unbhängige Menge dieses Graphen der Größe mindestens k gibt. (Eine unabhängige Menge ist eine Knotenmenge M , so dass je zwei Knoten aus M nicht durch eine Kante verbunden sind.) Welche der folgenden Aussagen gilt?
Was besagt der Gödelsche Unvollständigkeitssatz?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(T(M_w) \) regulär ist.
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(M_w \)auf Eingabe 11 auf allen Berechnungspfaden und auf jedem Band höchstens 42 Zellen besucht.
Welche der folgenden Einschränkungen an die äußere Form von Turingmaschinen (mit mehreren Bändern) stellt eine Einschränkung der durch solche Turingmaschinen akzeptierten Sprachen dar?
Sei f eine beliebige LOOP-berechenbare Funktion. Welche der folgenden Aussagen gilt nicht?
Seien A und B beliebige Sprachen. Welche der folgenden Aussagen gilt nicht?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) mit \(T(M_w) \neq \emptyset\) .
Sei a die Ackermann-Funktion
Welche Aussage gilt nicht?
\(\underline{\textit{Bekannte NP-vollständige Problem}}\)
- \(SAT\)
- \(3KNF-SAT\)
- \(CLIQUE\)
- \(Gerichteter\ Hamilton\ Kreis\)
- \(Mengenüberdeckung\)
- \(Färbbarkeit\)
- \(Knotenüberdeckung\)
- \(Partition\)
- \(Traveling \ Salesman\)
- \(Bin \ Packing\)
\(\underline{\textit{3KNF-SAT}}\)
gegeben: Eine Boolesche Formel \(F\) in konjunktiver Normalform (Klauselform) mit höchstens 3 Literalen pro Klausel
gefragt: Ist \(F\) erfüllbar?
\(\underline{\textit{Mengenüberdeckung}}\)
gegeben: Ein Mengensystem über einer endlichen Grundmenge \(M\), also \(T_1,...T_k \subseteq M\), sowie eine Zahl \(n \leq k\).
gefragt: Gibt es eine Auswahl aus \(n\) Mengen \(T_{i_1},...,T_{i_n}\), bei der bereits alle Elemente aus \(M\) vorkommen?
\(\underline{\textit{CLIQUE}}\)
gegebe: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\)
gefragt: Besitzt \(G\) eine "Clique" der Größe mindestens \(k\)? (Dies ist eine Teilmenge \(V'\) der Knotenmenge mit \(\vert V' \vert \geq k\) und für alle \(u,v \in V'\) mit \(u \neq v\) gilt: \(\{ u,v \} \in E\)).
\(\underline{\textit{Knotenüberdeckung}}\)
gegeben: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\).
gefragt: Besitzt \(G\) eine "überdeckende Knotenmenge" der Größe höchstens \(k\)? (Dies ist eine Teilmenge \(V' \subseteq V \) mit \(\vert V' \vert \leq k\), so dass für alle Kanten \(\{ u,v \} \in E\) gilt: \(u \in V'\) oder \(v \in V'\)).
\(\underline{\textit{Rucksack (oder SUBSET SUM)}}\)
gegeben: Natürliche Zahlen \(a_1, a_2, ..., a_k \in \mathbb{N}\) und \(b \in \mathbb{N}\).
gefragt: Gibt es eine Teilmenge \(I \subseteq \{ 1,2,..., k\}\) mit \(\sum _{i \in I} a_i = b\)?
\(\underline{\textit{Partition}}\)
gegeben: Natürliche Zahlen \(a_1, a_2,...a_k \in \mathbb{N}\)
gefragt: Gibt es eine Teilmenge \(J \subseteq \{ 1,2,...,k \}\) mit \(\sum_{i \in J} a_i = \sum _{i \notin J} a_i\)?
Was sind Platzschranken?
Eine nichtdeterministische Maschine mit Platzschranke \(f: \mathbb{N} \rightarrow \mathbb{N}\) besitzt keinen Algorithmus, die auf Eingabe der Länge \(n \geq 0\) mehr als \(f(n)\) Felder des Bandes benutzt. Für alle Platzschranken gilt \(f \in \Omega(log(n))\)
Was sind Zeitschranken?
Eine nichtdeterministische Maschine mit Zeitschranke \(f: \mathbb{N} \rightarrow \mathbb{N}\) besitzt keinen Algorithmus, die auf Eingabe der Länge \(n \geq 0\)mehr als \(f(n)\) Rechenschritte machen kann, bevor das Band hält. Es sind auch \(n+1\) Zeitschritte erlaubt, um zu erkennen, wann das Band endet
Welche Platzklassen gibt es?
\(\textbf{DSPACE}(f)\) und \(\textbf{NSPACE}(f)\) für \(f \in \Omega(log(n))\)
Welche Zeitklassen gibt es?
\(\textbf{DTIME}(f) \) und \(\textbf{NTIME}(f) \) für \(f(n) \geq n \ ; \forall n\)
\(\underline{\textbf{DTIME(t)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M\) mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) nach höchstens \(max \{ t(n),n+1 \}\)Schritten hält.
\(\underline{\textbf{NTIME(t)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M\) mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) und bei allen Rechnungen nach höchstens \(max \{ t(n),n+1 \}\)Schritten hält.
\(\underline{\textbf{DSPACE(s)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M \)mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) höchstens \(s(n)\) Arbeitsbandfelder benötigt.
\(\underline{\textbf{NSPACE(s)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M \)mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) bei allen Rechnungen höchstens \(s(n)\) Arbeitsbandfelder benötigt.
\(\underline{\textbf{Beispiele für DSPACE(log(n))}}\)
\( \{ a^nb^nc^n | n \geq 1 \} \\ \{ w\$ w | w \in \Sigma^* \} \)
Die Menge PRIMES mit PRIMES = \(\{ p \in 1 \{ 0,1 \} ^* | \ p \) ist Binärcodierung einer Primzahl
\(\underline{\textbf{Beispiele für Zeitkonstruierbarkeit}}\)
- Polynomfunktionen
- \(f(n)=2^{p(n)}\) und p ist Polynomfunktion
\(\underline{\textbf{Beispiele für Platzkonstruierbarkeit}}\)
\( \lceil log_a^k (n) \rceil , a \geq 2, k \geq 1 \\ \sqrt[5]{n} \)
\(\underline{\textbf{Zusammenhang zeit- und platzkonstruierbar}}\)
\(f \ ist \ zeitkonstruierbar \Rightarrow f \ ist \ platzkonstruierbar\)
\(\underline{\textbf{Satz von Hennie-Stearns }}\)
Sei \(\forall n : f(n) \geq n\) , dann gilt:
\(DTIME(f) \subseteq NTIME(f) \subseteq DSPACE(f) \)
Die Funktion \(f(n)=17n^3-6n^2+3n+23\)ist
Die Funktion \(f(n)=2^{2^n}\) ist
Gebräuchliche Abkürzung für DSPACE, NSPACE, DTIME, NTIME
\(\textbf{L}=\textbf{DSPACE}(log(n)) \\ \textbf{NL}=\textbf{NSPACE}(log(n)) \\ \textbf{P}=\bigcup_{k \geq 1} \textbf{DTIME}(n^k) \\ \textbf{NP}=\bigcup_{k \geq 1} \textbf{NTIME}(n^k) \\ \textbf{PSPACE}=\bigcup_{k \geq 1} \textbf{DSPACE}(n^k) = \bigcup_{k \geq 1} \textbf{NSPACE}(n^k) \)
Welche Varianten algorithmischer Probleme gibt es?
- Entscheidungsvariante
- Berechnungsvariante
- Optimierungsvariante
Grafik Beziehungen wichtiger Komplexitätsklassen
Grafik
\(\underline{\textit{Der Satz von Savitch}}\)
Sei \(s \in \Omega(log(n))\). Dann gilt:
\(\textbf{NSPACE}(s) \subseteq \textbf{DSPACE}(s^2) \)
\(\underline{\textit{Determenistischer Platzhierarchiesatz}}\)
Seien \(s_1, s_2: \mathbb{N} \rightarrow \mathbb{N} \) Funktionen, \(s_1 \notin \Omega (s_2), s_2 \in \Omega(log(n)) \) und \(s_2\) sei platzkonstruierbar. Dann gilt \(\textbf{DSPACE}(s_2) \backslash \textbf{DSPACE}(s_1) \neq \emptyset\) .
Alternativ:
\(\textbf{DSPACE}(f(n)) \subsetneq \textbf{DSPACE}(f(n) \cdot log(f(n)))\)
-
- 1 / 76
-
Lernkarten
Welche Varianten algorithmischer Probleme gibt es?
- Entscheidungsvariante
- Berechnungsvariante
- Optimierungsvariante
Grafik Beziehungen wichtiger Komplexitätsklassen
Grafik
\(\underline{\textit{Der Satz von Savitch}}\)
Sei \(s \in \Omega(log(n))\). Dann gilt:
\(\textbf{NSPACE}(s) \subseteq \textbf{DSPACE}(s^2) \)
\(\underline{\textit{Determenistischer Platzhierarchiesatz}}\)
Seien \(s_1, s_2: \mathbb{N} \rightarrow \mathbb{N} \) Funktionen, \(s_1 \notin \Omega (s_2), s_2 \in \Omega(log(n)) \) und \(s_2\) sei platzkonstruierbar. Dann gilt \(\textbf{DSPACE}(s_2) \backslash \textbf{DSPACE}(s_1) \neq \emptyset\) .
Alternativ:
\(\textbf{DSPACE}(f(n)) \subsetneq \textbf{DSPACE}(f(n) \cdot log(f(n)))\)
\(\underline{\textit{Deterministischer Zeithierarchiesatz}}\)
Seien \(t_1, t_2: \mathbb{N} \rightarrow \mathbb{N}\) Funktionen, \(t_1 \cdot log(t_1) \notin \Omega(t_2), \ t_2 \in \Omega(n \ log(n))\)und \(t_2\) sei zeitkonstruierbar. Dann gilt \(\textbf{DTIME}(t_2) \backslash \textbf{DTIME}(t_1) \neq \emptyset \).
Alternativ:
\(\textbf{DTIME}(f(n)) \subsetneq \textbf{DTIME}(f(n) \cdot log^2(f(n)))\)
\(\underline{\textit{Satz von Borodin}}\)
Sei r eine totale, berechenbare Funktion, \(r(n) \geq n\) für alle \(n\). Dann existiert effektiv eine totale, berechenbare Funktion \(s: \mathbb{N} \rightarrow \mathbb{N}\) mit der Eigenschaft \(s(n) \geq n+1\) für alle \(n\) und
\(\textbf{DTIME}(s) = \textbf{DTIME}(r \circ s)\).
\(\underline{\textit{Satz von Szelepcsenyi und Immerman}}\)
Sei \(f \in \Omega (log(n))\) dann gilt
\(\textbf{NSPACE}(f)=\textbf{CoNSPACE}(f)\)
\(\underline{\textit{Die Translationstechnik}}\)
Sei \(L \subseteq \Sigma^*\)eine Sprache, \(f:\mathbb{N} \rightarrow \mathbb{N}\) eine Funktion mit \(f(n) \geq n\) für alle \(n \geq 0\) und sei \(\$ \notin \Sigma\) ein neues Symbol. Definiere eine Sprache \(Pad_f(L)\) über dem erweiterten Alphabet \(\Sigma \cup \{ \$ \}\) durch
\(Pad_f (L) = \{w \$ ^{f(\vert w \vert)- \vert w \vert } \vert w \in L \}\).
Man beachte, dass auf diese Weise jedem Wort aus \(L\) mit Länge \(n\) ein Wort aus \(w\$^*\) der Länge \(f(n)\) zugeordnet wird.
\(\underline{\textit{Polynomialzeitreduktion (mit Grafik)}}\)
Grafik
\(\textit{Polynomialzeitreduktion}\)
Seien \(L \subseteq \Sigma^*\) und \(L' \subseteq \Sigma'^*\) zwei (Entscheidungs-)Probleme. Unter einer Reduktion des Problems \(L\) auf das Problem \(L'\) verstehen wir eine totale und berechenbare Abbildung \(f: \Sigma^* \rightarrow \Sigma'^*\) mit der Eigenschaft \(x \in L \Leftrightarrow f(x) \in L'\).
\(Was \ ist \ berechenbar?\)
Eine (evtl. partielle Funktion) \(f\colon \mathbb{N}^k \rightarrow \mathbb{N}\) ist berechenbar falls es ein Rechenverfahren bzw. Algorithmus gibt, das \(f\) berechnet, d.h. gestartet mit \( \mathbb{N}^k\) als Eingabe soll der Algorithmus nach endlich vielen Schritten mit der Ausgabe \(f(n_1, ..., n_k) \) stoppen
Was besagt die Churchsche These?
Die durch die formale Definition der Berechenbarkeit (Turing-, Loop-, While, GOTO, \( \mu \)-Rekursivität) erfasste Klasse von Funktionen stimmt genau mit der Klasse der im intuitiven Sinne berechenbaren Funktionen überein
Für die Berechenbarkeit gilt...
... dass ein Algorithmus existiert. Man muss ihn nicht explizit angeben.
Gilt für jede reelle Zahl r, das die zugeordnete Funktion \(f_r\) berechenbar ist?
Nein, denn es gibt überabzählbar viele reelle Zahlen, aber nur abzählbar viele Rechenverfahren. Je zwei verschiedene reelle Zahlen müssten dann zwei verschiedenen Rechenverfahren zugeordnet werden.
\(\underline{\textbf{Gödelscher Unvollständigkeitssatz}}\)
Jedes Beweissystem, durch das nur wahre arithmetische Aussagen beweisbar sind, ist notwendigerweise unvollständig.
\(\underline{Definition \ LOOP-Programm}\)
Eine Funktion \(f : \mathbb{N}^k \rightarrow \mathbb{N} \) heißt LOOP-berechenbar, falls es ein LOOP-Programm P gibt, das \(f\) in dem Sinne berechnet, dass P, gestartet mit \(n_1, \ ... \ , \ n_k \) in den Variablen \( x_1, ... , \ x_k \) (und 0 in den restlichen Variablen) stoppt mit dem Wert \(f(n_1, \ ... \ , \ n_k) \) in der Variablen \( x_0\).
\(\underline{Definition}\ von \ \textit{WHILE-Berechenbarkeit}\)
Eine Funktion \(f: \mathbb{N}^k \rightarrow \mathbb{N} \) heißt WHILE-berechenbar, falls es ein WHILE-Programm \(P\) gibt, das \(f\)in dem Sinne berechnet, dass \(P\), gestartet mit \(n_1,...,n_k\) in den Variablen \(x_1,...,x_k\) (und 0 in den restlichen Variablen) stoppt mit dem Wert \(f(n_1,...,n_k)\) in der Variablen \(x_0\) - sofern \(f(n_1,...,n_k)\) definiert ist, ansonsten stoppt \(P\) nicht.
\(\underline{Grafik:} \textit{GOTO, WHILE, TM und LOOP Zusammenhang}\)
Grafik
\(\underline{Satz:} \textit{Kleenesche Normalform für WHILE-Programme}\)
Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.
Eine Mehrband-Turingmaschine kann auf \( k \ge 1\) vielen Bändern unabhängig voneinander operieren, d.h. ...
sie hat \(k\) Schreib-Leseköpfe, die in jedem Schritt lesen, schreiben und sich unabhängig voneinader bewegen können. Sie besitzt nicht mehr "Berechnungskraft" als das Einfach-Modell.
\(\underline{\textit{Satz zu Mehrband-Turingmaschinen}}\)
Zu jeder Mehrband-Turingmaschine M gibt es einen (Einband)Turingmaschine M' mit T(M) = T(M') bzw. so dass M' dieselbe Funktion berechnet wie M.
Sind alle LOOP-Programme total?
Ja, denn jedes Programm stoppt zwangsläufig nach endlicher Zeit.
Sind alle totalen und intuitiven Funktionen LOOP-berechenbar?
Nein, die Ackermannfunktion ist total und berechenbar, aber nicht LOOP berechenbar.
Wie konstruiert man IF-THEN-ELSE durch ein LOOP-Programm?
\( IF \ x = 0 \ THEN \ A \ END\)
\(y:=1; \\ LOOP \ x \ DO \ y:=0 \ END; \\ LOOP \ y \ DO \ A \ END\)
\(\underline{\textit{Satz von Rice}}\)
Sei \(R\) die Klasse aller Turing-berechenbaren Sprachen. Sei \(\emptyset \neq S \subsetneq R\) eine beliebige echte Teilmenge. Dann ist die Sprache \(C(S)=\{ w \ \vert \ L(M_w) \in S \} \) unentscheidbar.
Praktisch: die Frage nach einer nicht-trivialen Eigenschaft einer Turingmaschine ist unentscheidbar. Eine nicht-trivial Eigenschaft ist hierbei eine Eigenschaft die für alle Turingmaschinen, unabhängig von ihrer Implementierung, gelten muss. Also eine Eigenschaft der Sprache und nicht der Turingmaschine selbst.
\(\underline{\textit{Gödelsches Prädikat}}\)
Für jede Zahlen \((n_0, ...,n_k)\)gibt es \(a\) und \(b\), so dass für \(i=0...k\) gilt:
\(n_i=a \ MOD \ (1+(i+1) \cdot b)\)
Gleichwertig zu \(\beta(a,b,i,n_i)\)ist wahr.
\(\underline{\textit{Entscheidbare und semientscheidbare Sprachen}}\)
Eine NTM \(M\) hält bei einer Eingabe \(x\), falls alle Rechnungen von \(M(x)\) eine endliche Länge haben.
Eine NTM \(M\) entscheidet eine Eingabe \(x\) falls \(M(x)\) hält oder eine Konfiguration mit einem Endzustand erreichen kann.
Eine Sprache \(L \subseteq \Sigma^*\) heißt entscheidbar, falls eine DTM \(M\) mit \(L(M)=L\) existiert, die jede Eingabe \(x \in \Sigma^*\) entscheidet.
Jede von einer DTM \(M\) erkannte Sprache heißt semientscheidbar.
Die von \(M\) akzeptierte Sprache \(L(M)\) heißt semientscheidbar, da \(M\) zwar alle Eingabe \(x \in L\) entscheidet, aber eventuell nicht alle \(x \in \bar{L}\)(Komplement von L).
Alle Typ-0 Sprachen sind semientscheidbar.
\(\underline{\textit{Charakteristische Funktion und Entscheidbarkeit}}\)
Eine Sprache \(A \subseteq \Sigma^*\) ist genau dann entscheidbar, wenn ihre charakteristische Funktion \(\chi _A :\Sigma^* \rightarrow \{ 0,1 \}\) berechenbar ist:
\(\chi_A(x) = \begin{cases} 1, & \text{für } x \in A \\ 0, & \text{für } x \notin A \end{cases}\)
Eine Sprache ist semientscheidbar, wenn ihre partielle charakteristische Funktion berechenbar ist.
\(\underline{\textit{WHILE-Programme}}\)
Eine Funktion \(f: \mathbb{N}^k \rightarrow \mathbb{N} \) nennt man WHILE-berechenbar, wenn es ein WHILE-Programm \(P\) gibt, das \(f\) wie folgt berechnet: \(P\) mit \(n_1...n_k\)in den Variablen \(x_1...x_k\) hält nach endlich vielen Schritten (wenn \(f(n_1...n_k)\) definiert ist) und dann befindet sich in der Variable \(x_0\) der Wert \(f(n_1...n_k)\). Falls nicht definiert, hält \(P\) nicht.
\(\underline{\textit{Welche Funktionen sind primitiv rekursiv?}}\)
- Konstante Funktionen
- Projektionen
- Nachfolgerfunktion \(s:\mathbb{N} \rightarrow \mathbb{N}\) mit \(s(n)=n+1\)
- Funktione die durch Einsetzen aus primtiv-rekursiven Funktionen entstehen
- Funktionen, die durch primitive Rekursion von primitiv rekursiven Funktionen enstehen
- Addition und Multiplikation
- Modifizierte Differenz
- Identifikation von Variablen
- Fiktive Variablen
- Vertauschte Variablen
- Einsetzen mit verschiedenen Variablen
\(\underline{\textit{Spezielle Regeln für Rekursion}}\)
- Eine Funktion ist genau dann primitiv rekursiv , wenn sie LOOP berechenbar ist. (primtiv rekursiv = LOOP-berechenbar)
- \(\mu\)-rekursiv = WHILE-berechenbar
\(\underline{\textit{Satz von Kleene}}\)
Sei \(f: \mathbb{N}^n \rightarrow \mathbb{N}\) eine \(\mu\)-rekursive Funktion. Dann existieren zwei \((n+1)\) stellige primitiv rekursive Funktionen \(p\) und \(q\) mit
\(f(x_1,...,x_n)=p(x_1,...,x_n,\mu q(x_1,...,x_n)) \).
\(\underline{\textit{Entscheidbar vs. Semientscheidbar}}\)
Eine Sprache \(A \subseteq \Sigma^*\)heißt entscheidbar genau dann, wenn \(A\) und \(\bar{A}\) semientscheidbar sind.
\(\underline{\textit{Rekursiv aufzählbare Sprachen}}\)
\(A \subseteq \mathbb{N}\) ist genau dann rekursiv aufzählbar, wenn sie die leere Menge ist (\(A = \emptyset\)) oder es eine totale und berechenbare Funktion \(f: \mathbb{N} \rightarrow \Sigma^*\) gibt, so dass gilt:
\(A=\{ f(n) \vert n \in \mathbb{N} \}\)
\(A\) ist genau rekursiv aufzählbar, wenn \(A\) semientscheidbar ist.
\(\underline{\textit{Äquivalente Charakterisierung einer rekursiv aufzählbaren Sprache}}\)
A ist rekursiv aufzählbar \(\Leftrightarrow\) A ist semientscheidbar \(\Leftrightarrow\) A ist von Typ 0 \(\Leftrightarrow\) A=T(M) für eine Turingmaschine M \(\Leftrightarrow\) \(\chi'_A\)ist berechenbar \(\Leftrightarrow\) A ist Definitionsbereich einer berechenbaren Funktion \(\Leftrightarrow\) A ist Wertebereich einer berechenbaren Funktion
\(\underline{\textit{Unentscheidbare Grammatik-Probleme}}\)
- Leehrheit des Schnitts: \(L_1 \cap L_2 = \emptyset \ ?\)
- Endlichkeit des Schnitts: \(\vert L_1 \cap L_2 \vert = \infty \ ?\)
- Kontextfreiheit des Schnitts: \(\exists G \ (Typ2) \ mit \ L(G)= L_1 \cap L_2 \ ?\)
- Inklusion: \(L_1 \subseteq L_2 \ ?\)
- Äquivalenz: \(L_1 = L_2 \ ?\)
\(\underline{\textit{Arithmetische Repräsentierbarkeit}}\)
\(f:\mathbb{N}^k \rightarrow \mathbb{N}\) ist arithmetisch repräsentierbar, wenn eine \((k+1)\)stellige arithmetische Formel \(F\) existiert, so dass
\(F(n_1,...,n_k,m) \Leftrightarrow f(n_1,...,n_k)=m\)
Jede WHILE-berechenbare Funktion ist arithmetisch repräsentierbar.
\(\underline{\textit{Satz von COOK}}\)
SAT ist NP-vollständig.
\(\underline{\textit{Sprachen, die weder Semi- noch CoSemi-entscheidbar sind}}\)
- \(U=\{ w:L(M_w) = \Sigma^* \}\)
- \(I=\{ w : \vert L(M_w) \vert = \infty \}\)
- \(Q= \{ (w_1, w_2) : L(M_{w_1}=L_{w_2} \}\)
\(\underline{\textit{Sprachen, die unentscheidbar sind}}\)
- \(E= \{ w: L(M_w) = \emptyset \}\)
- \(PCP\) Postsches Korrespondenzproblem
- Halteproblem \(H\), Halteproblem auf leerem Band \(H_0\)
