cards-deck: university::theo_complexity

Entscheidbarkeit von Sprachen // Berechenbarkeit von Funktionen:

part of [[112.00_anchor_overview]]

Bevor wir uns Entscheidbarkeit von Sprachen anschauen, werden wir aufzählbare/entscheidbare Sprachen nochmals betrachten:

Wiederholung aufzählbare / entscheidbare Sprachen:

Eine Sprache $L$ heißt (rekursiv)aufzählbar (oder auch semi-entscheidbar), falls es eine TM $M$ gibt, die die Sprache $L$ akzeptiert. Das heißt, dass jeweils gelten muss: formal betrachtet #card $w\in L⟹TM(w)=1$ akzeptiert das Wort und $w\notin L⟹TM(w)=0$ verwirft das Wort oder hält nicht an (Terminiert nicht[[theo2_TuringMaschineBasics#2 Endzustände:]]) ^1686523075270

Weiter nennen wir eine Sprache $L$ (rekursiv) entscheidbar, falls es eine TM $M$ gibt, so dass dann gilt: welche zwei Zustände müssen gelten? #card $w\in L⟹TM(w)=1$ akzeptiert das Wort oder $w\notin L⟹TM(w)=0$ akzeptiert das Wort nicht und verwirft es

Der große Unterschied besteht hier also darin, dass entscheidbare Sprachen auf jeden Fall eine terminierende TM haben, die entweder annimmt oder nicht. aufzählbare Sprachen hingegen haben eine TM, die entweder akzeptiert (und terminiert) oder ein Wort nicht annimmt und so entweder terminiert, oder auch nicht! ^1686523075281

Das ist eine Aussage, die wir über Sprachen treffen können, weiter möchten wir das jetzt aber auf Funktionen ausbreiten und schauen, ob man so auch entscheiden kann, ob eine Funktion von einer TM beschrieben werden kann, dass sie terminieren wird und die Ausgabe passend setzt, oder nicht.

Turing-Berechenbarkeit von Funktionen :

Eine Funktion $f:{\Sigma }^{\ast }⟶{\Gamma }^{\ast }$ heißt (Turing)-berechenbar oder auch total-rekursiv, falls es eine TM gibt, die :: bei der Eingabe von einem Wort $w\in {\Sigma }^{\ast }$ den Funktionswert $f(w)$, also das Ergebnis der Berechnung, ausgibt und terminiert! Ausgeben bedeutet hier, dass das Ergebnis der Funktion sich auf dem Band befinden soll! ^1686523075287 Wir sehen, dass hier auch eine Terminierung und Akzeptierende Charakteristik angestrebt und gefordert wird. Wir können nun betrachten, dass die Berechenbarkeit einer Funktion ungefähr gleich zur Entscheidbarkeit einer Sprache ist.

Entscheidbarkeit vs Berechenbarkeit :

Eine Sprache $L\subset {\Sigma }^{\ast }$ ist genau dann entscheidbar, welche charakteristische Funktion können wir dann setzen? #card wenn ihre charakteristische Funktion berechenbar ist! die charakteristische Funktion beschreiben wir wie folgt: $1_L:{\Sigma }^{\ast }⟶\{0,1\}$ $1_L(w)=\begin{array}{c}1,w\in L\text{akzeptiert!}\\ 0\text{sonst, nicht akzeptiert!}\end{array}$ Wir können also wahrscheinlich ein Entscheidbarkeitsproblem in ein Berechenbarkeitsproblem umwandeln! ^1686523075293

Beweis Entscheidbarkeit vs Berechenbarkeit :

Wir starten den Beweis mt der Implikation nach rechts: Beweis: $⟹$: L entscheidbar $⟹1_L$ berechenbar #card was wären weitere Schritte für den Beweis ? Grundsätzlich ist es eine einfache Implikation. Wir haben eine TM $M$, die $w$ genau dann akzeptiert, wenn $w\in L$, also in der Sprache enthalten ist. Wir erweitern diese TM folgendermaßen zu $M^{\sim }$ :: ^1686523075298

• Falls $M$ akzeptiert, schreibe eine 1 auf das Band und lösche alles andere, stoppe dann!
• Falls $M$ verwirft( also $w\notin L$), schreibe 0 auf das Band! ![[Pasted image 20230510230603.png]]

wir bauen quasi einen Wrapper, um unsere vorhandene Turingmaschine!

Jetzt haben wir die eine Implikation abgeschlossen, wie sieht die andere aus ? Beweis $⟸$: welche schritte sind nötig? #card Wir haben zuvor $M^{\sim }$ konstruiert, die $1_L$ berechnen kann (also 1 oder 0 ausgibt! ). Wenn diese TM eine 1 zurückgibt, dann begeben wir uns in den akzeptierten Zustand. Bei einer 0 in den verwerfenden Zustand! ![[Pasted image 20230510230821.png]] ^1686523075304

Ferner möchten wir jetzt noch eine Funktion beschreiben, die berechenbar sein soll, wenn wir eine TM finden können, die eine Sprache, die diese Funktion abbilden kann, entscheidet

Berechenbarkeit einer Funktion $⟹$ Entscheidbarkeit Sprache:

Eine Funktion $fL\Sigma ⟶{\Gamma }^{\ast }$ ist berechenbar genau dann, wenn es eine TM gibt, die die folgende Sprache entscheidet $L_f=\{w\#g|w\in {\Sigma }^{\ast },g\in {\Gamma }^{\ast },f(w)=g\}$ was wird mit dieser Sprache entschieden / gemeint? #card Wir beschreiben also eine neue Menge, die immer aus der Konkatenation einer Eingabe $w\in {\Sigma }^{\ast }$ einem Trennsymbol $\#$ und einer Ausgabe aus der Menge ${\Gamma }^{\ast }$ besteht. Ferner beschreiben wir die Sprache so, dass sie nur gültige Aus- und Eingabe -Tupel enthält , also nur die Werte von ${\Sigma }^{\ast }$ die in der Funktion $f$ zu einem Wort aus ${\Gamma }^{\ast }$ resultieren! ^1686523075309

Berechenbarkeit $⟶$ Entscheidbarkeit:

Eine Funktion $f:{\Sigma }^{\ast }⟶{\Gamma }^{\ast }$ ist berechenbar genau dann, wenn es eine TM gibt. die die folgende Sprache entscheidet: $L_f=\{w\#g|w\in {\Sigma }^{\ast },g\in {\Gamma }^{\ast },f(w)=g\}$ was wird mit dieser Sprache beschrieben? #card

• Hierbei ist $w$ Eingabe
• $\#$ ein Indikator, dass die Eingabe von der Ausgabe trennt
• $g$ das erwartete Wort Weiterhin können wir also Aussagen, dass eine Funktion $f$ als berechenbar gilt, wenn wir eine TM konstruieren können, die mit einer Entscheidung(Entscheidbarkeit) abgeschlossen wird ^1686523075314

Beweis Berechenbarkeit $⟶$ Entscheidbarkeit

Beweis $⟹$: was ist ein Ansatz um diese Implikation zu zeigen? #card Sei $f$ berechenbar d.h. es gibt einen $TM,M_1$ , die bei einer Eingabe $w\in {\Sigma }^{\ast }$ die Ausgabe $f(w)$berechnet. Wir konstruieren nun eine Turingmaschine $M_2$, welche als wrapper für unsere Eingabe agiert. In dieser haben wir eine weitere Turingmaschine $M_1$ welche $w$ verarbeitet und anschließend $g_1$ ausgibt –> $g_{!}$ entspricht dabei der Ausgabe dieser spezifischen, verarbeitenden Maschine. Anschließend vergleichen wir also ob die Ausgabe der gewünschten entspricht: $g_1{=}^{?}{g}_1$ Jenachdem, ob sie gleich sind oder nicht akzeptieren wir oder lehnen ab. ![[Pasted image 20230509124653.png]] ^1686523075319

Beweis $⟸$: wir haben die Implikation gezeigt, jetzt folgt die andere Seite. Wir haben zuvor bereits eine TM M_2 und M_1 gebaut, wobei M_2 die Eingabe w#g erhält und aus diesem dann dann g in eine zweite Turingmaschine M_1 speist. Am Ende werden beide verarbeitet #card Sei $M_2$ eine TM, die die Sprache $L_f$ entscheidet. Nun bauen wir daraus eine TM $M_1$ die $f$ berechnen soll. Dabei haben wir einen Ablauf ::
^1686523075323

1. Eingabe in $M_1$(TM 1) ist das Wort $w\in {\Sigma }^{\ast }$
2. Wir probieren der Reihe nach alle möglichen Antworten von $f(w)$ aus. Also:
   • ist $w\#ϵ$ ? ja/nein
   • ist $w\#0\in L_f$? ja/nein
   • ist $w\#1\in L_f$ ? ja/nein
   • so gehen wir jetzt alle Kombinationen durch! Dieser Ablauf wird so lange durchgegangen, bis wir eine richtige Antwort gefunden (troffen) haben. –> Laut unserer Definition, muss dieser Fall auf jeden Fall eintreten! Sobald wir also bei dieser Abfrage irgendwann ein Ja erhalten, dann weiß unsere Maschine M1 die Antwort zu der Eingabe! ![[Pasted image 20230510231827.png]] ^1686523075327