Berechenbarkeit und Komplexität

\(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.

\(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.

\( \{ 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

• Polynomfunktionen 
• \(f(n)=2^{p(n)}\) und p ist Polynomfunktion

\( \lceil log_a^k (n) \rceil , a \geq 2, k \geq 1 \\ \sqrt[5]{n} \)

\(f \ ist \ zeitkonstruierbar \Rightarrow f \ ist \ platzkonstruierbar\)

Sei \(\forall n : f(n) \geq n\) , dann gilt: 

\(DTIME(f) \subseteq NTIME(f) \subseteq DSPACE(f) \)

\(\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) \)

• Entscheidungsvariante
• Berechnungsvariante
• Optimierungsvariante

Grafik

Sei \(s \in \Omega(log(n))\). Dann gilt:

\(\textbf{NSPACE}(s) \subseteq \textbf{DSPACE}(s^2) \)

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)))\)

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)))\)

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)\).

Sei \(f \in \Omega (log(n))\) dann gilt

\(\textbf{NSPACE}(f)=\textbf{CoNSPACE}(f)\)

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.

Grafik

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'\).

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

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

... dass ein Algorithmus existiert. Man muss ihn nicht explizit angeben.

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.

Jedes Beweissystem, durch das nur wahre arithmetische Aussagen beweisbar sind, ist notwendigerweise unvollständig.

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\). 

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.

Grafik

Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.

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.

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.

Ja, denn jedes Programm stoppt zwangsläufig nach endlicher Zeit.

Nein, die Ackermannfunktion ist total und berechenbar, aber nicht LOOP berechenbar.

\(y:=1; \\ LOOP \ x \ DO \ y:=0 \ END; \\ LOOP \ y \ DO \ A \ END\)