cards-deck: university::theo_complexity

Sprachen die nicht rekursiv aufzählbar / semi-entscheidbar sind :

specific part of [[theo2_SprachenUnendlichkeit]] broader part of [[112.00_anchor_overview]]

Für diesen Teil ziehen wir nochmals in Betracht, was [[theo2_TuringMaschineBasics#rekursiv aufzählbar ::|Rekursiv aufzählbare Sprachen sind]] ^1686580402330 Folglich setzen wir nun ein festes, endliches Alphabet voraus, welches üblicherweise der Menge ${0, 1}$ entspringt.

Notation R und RE:

Wir betrachten mit der dem endlichen Alphabet nun Sprachen über diesem Alphabet.

$RE$ = definiert :: dann die Menge der rekursiv aufzählbaren bzw. semi-entscheidbaren Sprachen ^1686580402333

$R$ = entspricht der Menge, :: der rekursiv entscheidbaren Sprachen. ^1686580402336

Weiterhin können wir noch eine Menge aller regulären Sprachen definieren wie? #card
$REG =$ Menge der regulären Sprachen ![[Pasted image 20230516125308.png]] ^1686580402340

Satz : nicht rekursiv aufzählbare Sprachen

Wir betrachten das Alphabet $Σ = {0, 1}$ . Es gibt Sprachen $L$ über $Σ$ , die nicht rekursiv aufzählbar sind. warum? wie können wir diese Idee beweisen und zeigen? #card Einen Beweis finden wir folgend:

Die Menge aller Turingmaschinen (Gödelnummern) ist bekannt abzählbar unendlich
Also ist die Menge der Sprachen, die von einer TM erkannt werden, auch höchstens abzählbar - denn wir können das Abzählbarkeitsargument anwenden
Die Menge aller Sprachen über ${0, 1}$ ist, wie zuvor betrachtet, überabzählbar –> Problem
Denn es muss (viele) Sprachen geben, die nicht von einer TM erkannt werden können. Schematisch betrachten würde es folgend aussehen: ![[Pasted image 20230516132801.png]]

Die meisten Sprachen sind nicht rekursiv aufzählbar und erst recht nicht rekursiv entscheidbar ^1686580402343

Diese Antwort ist nicht optimal, bzw nicht greifbar. Aus diesem Grund besteht die Motivation eine Sprache $D$ zu finden, welche eventuell $D \neq \in RE$ ist, um dann zeigen zu können, dass unsere Annahme stimmt? #card
nicht wirklich intuitiv, könne man jetzt die Diagonale Betrachtungsweise, wie beim Beweis von überabzählbaren Elementen in $R$ anschauen und daraus eine Sprache generieren, die ebenfalls nicht akzeptiert wird! Die Idee ist also:

Seien $w_{1}, w_{2}, w_{3}, \dots, w_{n}$ all Wörter über dem Alphabet $Σ = {0, 1}$ – wir wissen hier dass es nur abzählbar viele gibt, deswegen können wir die ganzen Wörte numerieren!
Weiterhin betrachten wir die Folge der existierenden Turing-Maschinene $M_{1}, M_{2,} \dots$ an –> auch da wissen wir, dass sie abzahlbar sind, gemäß früherer Betrachtungen. ^1686580402346

Wir definieren jetzt $d_{ij} = 1 falls Mi, das Wort wj akzeptiert 0, sonst$ Also wir betrachten wieder eine Matrix, welche zum einen die ganzen TMs und die ganzen Wörter auflistet. Für jede Kombination entscheiden wir nun ob sie akzeptiert wird oder nicht (die $T M_{i}$ akzeptiert Wort $w_{j}$ oder nicht).

TM	$w_{1}$	$w_{2}$	$\dots$
$M_{1}$	$d_{11}$	$d_{12}$	$\dots$
$M_{2}$	$d_{21}$	$d_{22}$	$\dots$
$\dots$	$\dots$	$\dots$	$\dots$

in der $i$ -ten Zeile steht dann immer der Indikatorvektor, der von $M_{i}$ akzeptierten Sprache. Nun definieren wir eine Sprache $D$ auf dieser Betrachtung.

$D = {w_{i} ∣ d_{ii} = 0}$ also das Wort, was immer Diagonal auf der Zeile ist, soll nicht akzeptiert werden –> also verwerfen!

TM	$w_{1}$	$w_{2}$	$w_{3}$
$M_{1}$	1	0	0
$M_{2}$	0	1	0
$M_{3}$	1	1	0
$\dots$

–> diese Sprache enthält in dem obigen Beispiel also nur $w_{3}$ und sonst keine Wörter Wir können hieraus jetzt zeigen, dass diese Sprache nicht von $M_{1}$ akzeptiert wird, denn da ist das Wort enthalten. Diese Folgerung können wir jetzt für alle Wörter fortführen und resultieren dann: Es gibt keine TM, die D erkennt.

Also $D \neq \in RE$ , d.h. die Diagonalsprache ist nicht rekursiv aufzählbar!

erneute Betrachtung der Struktur: Betrachten wir folgendes:

$M_{1}, M_{2} \dots$ sind die Turingnummern in der natürlichen Ordnung
$w_{1}, w_{2}, w_{3}$ sind die binären Strings in der natürlichen Ordnung
wir probieren nun aus, was das Ergebnis von $⟨ M_{i}, w_{i} ⟩$ ist: Falls gilt $⟨ M_{i}, w_{i} ⟩ = 1; w_{i} \neq \in D$ –> Denn das wort wird von der Tm erkannt, und ist so nicht in der Sprache enthalten Andereseits gilt: $= 0; w_{i} \in D$ -> also das WOrt ist in D enthalten, wenn die TM es nicht lesen kann.

Können wir für alle Wörter herausbekommen, ob sie in D sind und D auf diese Weise sogar entscheiden?

Diese gegebene Struktur sollte bis jetzt eigentlich funktionieren, aber das wird sie spätestens mit folgendem Beispiel nicht mehr: TM erhält ihre Turingnummer als Eingabe: Sei $M_{D}$ die TM, die wir gerade konstruiert haben. Sei $i_{0}$ der Index, den diese TM in der Liste aller TMs hat: $M_{1}, M_{2} \dots, M_{i_{0}} \dots$ –> also wir suchen den Index passend heraus nun nehmen wir das passende Wort : $w_{i_{o}}$ , was das das $i_{0}$ -ste Wort in unserer Liste aller Wörter ist. Das Ergebnis von $⟨ M_{i_{0}}, w_{i_{0}} ⟩$ ist nun ? Egal was wir nun folgern, es wird einen Widerspruch geben:

$M_{i_{0}}$ akzeptiert $w_{i_{0}} ⟹ D$ sollte das Wort nicht akeptieren, jedoch $D = M_{i_{0}}$ was ein Widerspruch ist
$M_{i_{0}}$ akzeptiert $w_{i_{0}} ni c h t ⟶ D$ sollte $w_{i_{0}}$ akzeptieren, aber dennoch $D = M_{i_{0}}$ was auch ein Widerspruch ist

Wir folgern diese Aussage, weil der Raum der möglichen TMs einfach zu klein ist, um für alle Wörter passende Abdeckung finden zu können!

Dieses Beispiel ist eventuell nicht 100% einleuchtend, weswegen wir weitere Beispiele betrachten, die nicht wirklich erkannt bzw. entschieden werden können:

Post’sches Korrespondenzproblem :

Gegeben seien $m$ verschiedene Typen von Dominosteinen -> zwei Seiten mit Symbolen drauf. Wir haben $u_{1}, \dots, u_{m}$ und $v_{1}, \dots, v_{n}$ feste Wörter über einem gegebenen Alphabet $Σ$ Wir haben von jedem Dominostein beliebig viele zur Verfügung. Frage: Gibt es eine endliche Folge von Dominosteinen, so dass das Wort oben identisch ist mit dem Wort unten also ![[Pasted image 20230516125733.png]] ? #card Wir können passend resultieren: Das Post’sche Korrespondenzproblem ist unentscheidbar. Wir können theoretisch naiv probieren, ob wir das Problem lösen können. Weiterhin gibt es jedoch keinen Algorithmus, der dieses Problem lösen bzw tatsächlich entscheiden kann! Wir wissen also nicht, ob es tatsächlich eine Lösung gibt, denn wir können es nicht algorithmisch beweisen! ^1686580402350

Warum können wir nicht sagen, ob tatsächlich eine Lösung für das Problem besteht oder nicht? Wo liegt das Problem, dass es nicht entscheidbar macht? #card Eine Begründung liegt darin, dass es unendlich viele Konstellationen gibt, die ausprobiert werden könnten/müssten . Da wir aber nicht wissen, ob unsere Turing-maschine, die entscheiden soll ob es geht oder nicht, terminieren wird und uns eine Lösung gibt (1 oder 0) oder einfach immer weiter suchen wird, ist es nicht entscheidbar.

Wir wissen nicht, ob unsere TM terminiert oder ewig bzw. sehr lange weitersuchen wird, da uns nicht obliegt, ob sie immernoch nach einem Ergebnis sucht oder nichts finden wird. ^1686580402353

Nach selbigen Prinzip ist auch Consway Game of Life aufgebaut, bzw die Frage, ob wir eine beliebige Startkonfig finden können, die passend mit einer gegebenen Zielkonfiguration resultieren wird.

Warum ist es eine Sprache, wenn wir nicht wissen, ob sie Wörter beinhaltet oder nicht

Wir können die Definition der Sprache setzen und brauchen jedoch eine Turingmaschine, die validiert, dass diese Sprache denn richtig definiert wurde bzw. können wir damit herausfinden, ob die vorgegebenen Wörter überhaupt in dieser enthalten sind.

Gibt es Sprachen in $RE ∖ R$ ?

![[Pasted image 20230516145543.png]] Um dies beantworten zu können, müssen wir eine weitere, wichtige Sprache definieren:

Definition $A_{TM}$ :

Sei $A_{TM} = {⟨ M, w ⟩ ∣ M ist Code einer TM und Wort w wird von M akzeptiert} \subset {0, 1}$ was beschreibt diese definierte Menge? Was können wir dann aus dieser ziehen? #card Also eine Submenge unseren Überabzählbaren Menge von Sprachen! Hier steht $⟨ M, w ⟩$ für das Wort, das die Gödelnummer der TM M mit Wort $w$ konkateniert. Wir werden sehen, dass $A_{TM}$ semi entscheidbar ist und tatsächlich eher nicht-entscheidbar xd ^1686580402356

Semi-Entscheidbarkeit von $A_{TM}$ :

Wir werden sehen, dass $A_{TM} \in RE$ . warum?, wie können wir einen Beweis dafür konstruieren? #card Um das zu zeigen, müssen wir eine TM bauen, die $A_{TM}$ aufzählen kann: $x \in A_{TM} ⟹ M$ akzeptiert und weiterhin $x \neq \in A_{T} M ⟹ M$ verwirft oder stoppt nicht. Hierzu können wir einfach eine universelle TM benutzen. Wir geben dieser $TM = U$ das Wort $⟨ M, x ⟩$ als Eingabe. Wir haben $U$ genau so konstruiert, dass sie nun akzeptieren würde, wenn der gegebene Code $M$ gültig ist und weiter $M (w) = 1$ akzeptiert! Wir sprachen nur von semi-entscheidbar und wollen folgend noch zeigen, dass sie nicht entscheidbar ist! ^1686580402360

Nicht-Entscheidbarkeit von $A_{TM}$ :

$A_{TM} \neq \in R$ –> wir würde denn eine TM $H$ aussehen, sodass sie $A_{TM}$ entscheiden könnte? #card Ihre Strukur müsste, wie folgt sein: $A_{TM}$ akzeptiert $⟺ H$ akzeptiert | und weiterhin auch $A_{TM}$ akzeptiert nicht $⟺ H$ verwirft also weiter könne daraus folgende Implikation entstehen! $A_{TM}$ verwirft $⟹ H$ verwirft $A_{TM}$ hält nicht $⟹ H$ verwirft

das sieht nicht gesund aus, wir können nicht entscheiden, ob sie tatsächlich terminieren wird oder nicht! Schade schokolade ^1686580402363

Beweis der Nicht-Entscheidbarkeit :

Angenommen die $A_{TM}$ ist entscheidbar. Dann sei $H$ eine TM, die $A_{TM}$ entscheidet. also: $H (⟨ M, w ⟩) (akzeptiert, falls M w akzeptiert verwirft, falls M w nicht akzeptiert)$ wir können jetzt wieder eine Matrix aufbauen und so die einzelnen Fälle betrachten:

H	$⟨ M_{1} ⟩$	$⟨ M_{2} ⟩$	$⟨ M_{3} ⟩$
$M_{1}$	acc	rej	acc
$M_{2}$	acc	rej	rej
$M_{3}$	rej	acc	rej

Also unsere Turing-Maschine hält immer an!, denn sie findet eine TM, die akzeptieren wird schauen, wir jedoch auf die Diagonale der Elemente. Wir können jetzt eine passende TM $D_{TM}$ konstruieren, mit folgenden Eigenschaften:

$D_{TM}$ bekommt den Code $⟨ M ⟩$ einer TM als Eingabe
$D_{TM}$ schaut was $H$ auf der Eingabe $⟨ M, ⟨ M ⟩⟩$ machen würde–> was ist die Diagonale Resolution??
$D_{TM}$ gibt dann genau das Gegenteil von H zurück:
- H azkeptiert –> $D_{T} M$ verwirft
- $H$ verwirft -> $D_{TM}$ akzeptiert

Wenn wir jetzt $D_{T} M$ auf sich selbst anwenden, was passiert dann? also $D_{TM} (⟨ D_{TM} ⟩) = a cce pt$ , dann müsste in der Tabelle von $H$ ein accept stehen, aber dann müsste gemäß der Definition von $D_{T} M$ dort verworfen wurden! Wenn jetzt aber $D_{TM} (⟨ D_{TM} ⟩) =$ reject, dann können wir gleih argumentieren und folgern und argumentieren, dass dies der Definition von $D_{TM}$ widerspricht.

wir haben also gezeigt, dass $D_{TM}$ nicht entscheidbar ist! was folgern wir daraus? #card ![[Pasted image 20230516151457.png]] Wir haben also eine Sprache $\in RE ∖ R$ gefunden! ^1686580402368

Mit dieser Betrachtung können wir jetzt auch Komplemente von Sprachen entwickeln: [[theo2_SprachenKomplement]]

scattered-lenity