date-created: 2024-06-18 12:22:41 date-modified: 2024-06-18 01:27:08

Unentscheidbare Probleme

anchored to 112.00_anchor_overview

Tags: #computerscience #complexitytheory
proceeds from 112.18_Satz_von_rice

Overview

-> Der Satz von Rice sagt, dass die “meisten spannenden Probleme” - alle nichttrivialen, semantischen - nicht entscheidbar sind.

Daher können wir dann folgern: -> Es gibt eine Vielzahl von unentscheidbaren Problemen, die sich auf die Berechenbarkeit von Funktionen und Sprachen beziehen.

Wir wollen diverse

Post’sche Korrespondenzproblem

von Emil Leon Post bewiesen / gesetzt. Vom Prof wurde hier auch wieder ein historischer Kontext gegeben, was praktisch ist. (Hatte manische Depression, ist an Elektroschock-Therapie gestorben).

[!Definition]

Sei $\Sigma$ ein alphabet mit mindestens 2 Symbolen, über dem Alphabet.

Gegeben sei eine Liste von Tupeln $\{({\alpha }_1,{\beta }_1),\dots ({\alpha }_k,{\beta }_K)\}$ aus Wörtern, ${\alpha }_i,{\beta }_i\in {\Sigma }^{\ast }$

Wir formulieren das Problem, so dass wir beliebige Steine so anordnen möchten, dasss die Zeichen, die sie oben abbilden, genau gleich der Sequenz, die unten ist, ist.

Wann haben wir etwa eine Lösung gefunden, wie wird sie beschrieben? #card

Eine Lösung solcher Sequenzen von Indices $\{i_k{\}}_{1\le k\le K}\in {\sigma }^{\ast }$ mit $K\ge 1,1\le i_k\le N$ für alle $k$. Wir knnen also beliebige Wortpaare so kombinieren, dass wir am Ende “oben und unten die gleichen Sequenzen stehen haben”.

Beispiel Wir nehmen dabei eine endliche Auswahl dieser und ferner möchten wir dann schauen, ob man die Steine so anordnen können:

[!Req] Das Problem ist Unentscheidbar

Also die Sprache ist unentscheidbar: $$PCP=\{A,B\mid \text{ Es existiert eine Lo¨sung}\}\notin R$$

Warum ist diese Sprache so schwer? Können wir sie aufzählen? #card

Wir können sie rekursiv aufzählen, weil jede mögliche Nummerierung garantiert ausgegeben wird - also wir können einen Aufzähler bauen - und damit wissen wir, dass sie $\in RE$ ist.. Ferner müssen wir aber noch zeigen, dass es nicht entscheidbar ist!

(Das machen wir, indem wir eine Brücke zwischen den Tms und ferner auch den Dominosteinen)

–> Wenn wir schon viele ausprobiert haben und keine Lösung gefunden haben, wissen wir nicht, ob nicht doch irgendwann eine kommt -> Problem des Halteproblems!

Modifizierte PCP | MPCP

Wir wollen das Problem etwas anpassen, damit wir folgend auf Turing-Maschinen reduzieren und dann zeigen können, dass wir hier nicht entsprechend eine Entscheidbarkeit folgern können.

[!Bemerkung]

Sei $\Sigma$ ein Alphabet mit mindestens 2 Symbolen.

Wie definieren wir die erweiterte Form des PCP? #card

Gegeben sei eine Liste von Tupeln $\{({\alpha }_1,{\beta }_2)\dots ,({\alpha }_n,{\beta }_n)\}$ aus Wörtern ${\alpha }_i,{\beta }_i\in {\Sigma }^{\ast }$ mit $K\ge 1,1\le i_k\le N$ für alle $k$ -< jedes Wortpaar kann man beliebig oft verwenden!, sodass dann etwa ${\alpha }_{i_1},\dots a_{i_k}={\beta }_{i_1}\dots {\beta }_{i_k}$? Ferner $i_1=1$? –> Wir setzen einen bestimmten Stein als Startstein, welcher immer als erstes gesetzt wird!

Reduktion

In der Reduktion können wir mindestens eine Instanz finden, wo wir nicht halten - sie nicht entscheiden können - und damit ist später automatisch die ganze Menge nicht mehr entscheidbar!

Wie wird der Anfang gewählt -> bei uns $=1$. Das kann man beliebige konstruieren –> Wir setzen ein beliebiges Steinchen aus der Menge aller, als den Anfang der Wörter

Damit können wir dann konstruieren und sagen, dass bei der Übersetzung unserer Dominosteine am Anfang garantiert dieser Start-Dominostein gesetzt wird und somit die Übersetzung immer gleich anfangen muss!

Turing-Äquivalenz von PCP

Wir wollen jetzt eine Turing-Maschine bauen, die genau auf diesem Konzept aufbauen kann bzw. es übersetzt. Dadurch können wir dann zeigen, dass das Problem gleich einer turing-Maschine ist und somit auch limitiert!

Wir beschreiben mit den Dominosteinen dann oben immer die aktuelle Ausführung - den aktuellen Schritt - und ferner unten dann den nächsten Schritt in unserer TM.

Etwa bei Rechts springen wir von Zustand $q$ unter Betrachtung der Eingabe $a$ und gehen dann nach rechts über also $\delta (q,a)=(r,b,R)$, wobei r die Eingabe rechts von a und b die nächste ist. Der Dominostein hat dann also $$\begin{array}{r}\text{ oben}:qa\\ \text{ unten}:br\end{array}$$ und somit beschrieben wir den Übergang.

#nachtragen

Wir können dann immer Steine nehmen (gelesen von links nach rechts), welche jetzt eine TM codieren bzw ihr Verhalten beschreiben kann wird.

wir haben bestimmte “Löschsteinchen”, die beim erreichen des akzeptierenden Zustandes dann dazu beitragen können, dass wir die formale Struktur der TM etablieren und somit festlegen können.

Sidenote: Es wurde bewiesen, dass ab $n>5$ das $PC{P}_n$ Problemn - also mit $n$ vielen verschiedenen Karten, nicht mehr entscheidbar ist. Für $n=2$ ist es entscheidbar und für $n=3,4$ weiß man es - noch - nicht. Beweis dazu etwa bei undecidability_binary_tag_systems_pcp

Konsequenzen der Äquivalenz von PCP

Die Unentscheidbarkeit gilt schon für das Alphabet Alphabet $\Sigma =\{0,1\}$ ( das kleinste, was wir betrachten haben, beschrieben mit $01-PCP$) Da alle anderen Alphabet die wir konstruieren können, am Ende durch Binärsymbole kodiert werden können!

Bezug zu Unentscheidbarkeitsbeweise für Grammatiken

Mit obiger Betrachtung können wir jetzt entscheiden, dass für zwei kontextfreie Grammatiken $G_1,G_2$ unentscheidbar ist, ob $L(G_1)\cap L(G_2)=\varnothing$

Das können wir durch eine Reduktion zeigen: Wir reduzieren das PCP Problem auf diese Entscheidbarkeit der Sprachen (und da wir schon wissen, das PCP schwer ist), wird dann auch diese Entscheidung schwer sein!

Gegeben sei ein beliebiges PCP $K=\{\dots \}$ eine Liste von Dominosteinen.

Wir wollen das auf ein Problem der Schnittmenge der Grammatiken bauen. Dafür müssen wir also die Grammatiken mit den Dominosteinen bauen

–> Wir bauen zuerst die erste Grammatik:

Wir generieren folgende Symbole $\Sigma =\{0,1,\$,a_1,\dots a_n\}$ dabei ist$a_1,\dots a_n$ eine Menge, die die Dominosteine lablen kann –> sie gibt also einen Index an.

daraus könenn wir dann durh Abbildungen der Variablen verschiedene Wörter beschreiben und bilden.

Die Sprache besteht aus Wörtern, wo immer erst der Eintrag eines Dominosteines gesetzt und danach sein Indize gesetzt wird. Auf der rechten Seite werden wir selbiges, aber für die unteren Einträge eines Dominosteines bestimmen. –> Dabei können diese Steine unterschiedlich sein, also $((a_1,a_2{a}_3\dots )(b_1,b_2,b_3\dots ))$

Damit könenn wir dann links und rechts jeweils betrachten und später vergleichen, ob sie gleich sind –> damit können wir mehr oder weniger de nSchnitt beschreiben.

Damit erzeugen wir also eine Sprache $$L_2=\{uv\$\hat{v}\hat{u}\mid u\in \{a_1,\dots ,a_n\},v\in \{0,1{\}}^{\ast }\}$$

Wenn wir eine Lösung für das Dominostein-Problem finden können, dann wird dadurch auch eine Lösung von dem Grammatik-Problem gefunden. Wir wissen, aber, dass es unentscheidbar ist und weil wir entsprechend reduziert haben, ist somit auch dieses Problem nicht entscheidbar!

Folgerungen :

#nachtragen

Wang-Fliesen | weiteres Beispiel

Teils auch als ein weiteres Domino-Problem beschrieben, weil die Idee ähnlich ist.

Wie kann man das beweisen? Man kann auch hier wieder eine Turingmaschine konstruieren, und somit die Fliesen auf eine TM reduzieren –> Dadurch findet auch das Halteproblem wieder statt, weswegen wir es ferner nicht entscheiden können!

Dafür gibt es eine Konstruktion, die von einer Person bewiesen wurde, jedoch ist der Name dieser unbekannt 15_Wang_tilings_reduced_to_TM

#nachtragen Beweisen:

Wir fangen an einer Kachel an. Und bauen rechts von ihr verschiedene / weitere Kachel hinein, die dann die Eingabe darstellt -> das können wir dann immer fortführen.

Schreibt man etwa einen Buchstaben auf das Band, dann setzt man eine neue Kachel über den Zustand und rückt nach oben rechts und kann da auf dem eeren Wort fortfahren. Wir bauen quasi ins unendlich diagonal nach oben rechts und wenn das zubauen ist, dann kann man ferner eine Fliese betrachten, die eine solche Fliese ist!

Matrix-Mortalitätsproblem

Angenommen wir haben ne Menge von Matrizen und wir wollen schauen, ob es ein Produkt von Matrizen aus der Menge gibt, sodass das Produkt dann 0 ist

Conways Game of Life

Frage, ob eine bestimmte Startkonfiguration in eine bestimmte Endkonfiguration übergeht, können wir nicht entscheiden.