anthropic/claude-opus-4.1

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Beweis:

Wir zeigen die Aussage durch Widerspruch.

Annahme: Beide Sprachen ABA \cup B und ABA \cup \overline{B} sind entscheidbar.

Wenn beide Sprachen entscheidbar sind, dann ist auch ihr Schnitt entscheidbar (der Schnitt entscheidbarer Sprachen ist entscheidbar).

Betrachten wir den Schnitt:
(AB)(AB)(A \cup B) \cap (A \cup \overline{B})

Nach den Distributivgesetzen der Mengenlehre gilt:
(AB)(AB)=A(BB)=A=A(A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) = A \cup \emptyset = A

Das bedeutet: Wenn sowohl ABA \cup B als auch ABA \cup \overline{B} entscheidbar wären, dann wäre auch AA entscheidbar.

Dies ist ein Widerspruch zur Voraussetzung, dass AA unentscheidbar ist.

Daher muss mindestens eine der beiden Sprachen ABA \cup B oder ABA \cup \overline{B} unentscheidbar sein.

Die Aussage ist somit wahr.

anthropic/claude-sonnet-4

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
The statement is **true**.

**Proof by contradiction:**

Assume both A ∪ B and A ∪ B̄ are decidable. Then there exist TMs M₁ and M₂ that decide these languages respectively.

For any string w ∈ Σ*, we have exactly three possible cases:
- Case 1: w ∈ A → M₁(w) = accept, M₂(w) = accept
- Case 2: w ∉ A, w ∈ B → M₁(w) = accept, M₂(w) = reject  
- Case 3: w ∉ A, w ∉ B → M₁(w) = reject, M₂(w) = accept

We can construct a decider for A: given input w, run both M₁ and M₂, then accept iff both accept.

This contradicts the undecidability of A. Therefore, at least one of A ∪ B and A ∪ B̄ is undecidable.

deepseek/deepseek-chat-v3.1

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Angenommen, sowohl ABA \cup B als auch ABA \cup \overline{B} sind entscheidbar. Da entscheidbare Sprachen unter Schnitt abgeschlossen sind, ist auch (AB)(AB)(A \cup B) \cap (A \cup \overline{B}) entscheidbar. Es gilt:
(AB)(AB)=A(BB)=A=A.
(A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) = A \cup \emptyset = A.

Somit wäre AA entscheidbar, was ein Widerspruch zur Voraussetzung ist, dass AA unentscheidbar ist. Daher muss mindestens eine der Sprachen ABA \cup B oder ABA \cup \overline{B} unentscheidbar sein.

deepseek/deepseek-r1-0528

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Die Aussage ist wahr. Wir beweisen dies durch Widerspruch.

Angenommen, sowohl ABA \cup B als auch ABA \cup \overline{B} sind entscheidbar. Dann gilt:
A=(AB)(AB).
A = (A \cup B) \cap (A \cup \overline{B}).

Begründung:
- Ist xAx \in A, so ist xABx \in A \cup B und xABx \in A \cup \overline{B}, also x(AB)(AB)x \in (A \cup B) \cap (A \cup \overline{B}).
- Ist x(AB)(AB)x \in (A \cup B) \cap (A \cup \overline{B}), so folgt:  
  Wäre xAx \notin A, dann müsste xBx \in B (aus xABx \in A \cup B) und xBx \in \overline{B} (aus xABx \in A \cup \overline{B}) gelten, was unmöglich ist. Also ist xAx \in A.

Da die entscheidbaren Sprachen unter Schnitt abgeschlossen sind, ist (AB)(AB)(A \cup B) \cap (A \cup \overline{B}) entscheidbar. Somit wäre AA entscheidbar, im Widerspruch zur Voraussetzung. Daher muss mindestens eine der Sprachen ABA \cup B oder ABA \cup \overline{B} unentscheidbar sein.

google/gemini-2.5-pro

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Die Aussage ist wahr.

Beweis:
Wir führen einen Widerspruchsbeweis. Angenommen, die Aussage sei falsch. Das würde bedeuten, dass es eine unentscheidbare Sprache AA und eine Sprache BB gibt, für die sowohl ABA \cup B als auch ABA \cup \overline{B} entscheidbar sind.

Seien L1=ABL_1 = A \cup B und L2=ABL_2 = A \cup \overline{B}. Nach unserer Annahme sind L1L_1 und L2L_2 entscheidbare Sprachen.

Die Klasse der entscheidbaren Sprachen ist unter der Schnittmengenbildung abgeschlossen. Das bedeutet, wenn L1L_1 und L2L_2 entscheidbar sind, dann ist auch ihre Schnittmenge L1L2L_1 \cap L_2 entscheidbar.

Betrachten wir nun die Menge L1L2L_1 \cap L_2. Mithilfe der Distributivgesetze der Mengenlehre können wir den Ausdruck vereinfachen:
L1L2=(AB)(AB)=A(BB) L_1 \cap L_2 = (A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) 
Der Schnitt einer Sprache BB mit ihrem Komplement B\overline{B} ist immer die leere Menge, d.h. BB=B \cap \overline{B} = \emptyset.
Somit gilt:
L1L2=A=A L_1 \cap L_2 = A \cup \emptyset = A 
Wir haben also gezeigt, dass die Sprache AA identisch ist mit der Sprache L1L2L_1 \cap L_2. Da L1L_1 und L2L_2 entscheidbar sind, muss auch ihr Schnitt AA entscheidbar sein.

Dies steht jedoch im Widerspruch zur Voraussetzung, dass AA unentscheidbar ist.
Unsere Annahme, dass sowohl ABA \cup B als auch ABA \cup \overline{B} entscheidbar sind, muss daher falsch sein. Folglich muss mindestens eine der beiden Sprachen unentscheidbar sein.

openai/gpt-5

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Beweis: Angenommen, sowohl ABA \cup B als auch ABA \cup \overline{B} seien entscheidbar. Dann ist auch ihr Durchschnitt entscheidbar. Es gilt
(AB)(AB)  =  A(BB)  =  A.
(A \cup B) \cap (A \cup \overline{B}) \;=\; A \cup (B \cap \overline{B}) \;=\; A.

Damit wäre AA entscheidbar — Widerspruch zur Voraussetzung. Also können nicht beide Vereinigungen entscheidbar sein; mindestens eine von ihnen ist unentscheidbar.

openai/gpt-oss-120b

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Beweis (Wahrheit der Aussage).

Seien A,BΣA,B\subseteq\Sigma^{*} beliebig und sei AA unentscheidbar.  
Wir zeigen, dass es unmöglich ist, dass beide Sprachen  

ABundAB
A\cup B \qquad\text{und}\qquad A\cup\overline{B}


entscheidbar sind.

Angenommen, sowohl ABA\cup B als auch ABA\cup\overline{B} seien entscheidbar.  
Die Klasse der entscheidbaren Sprachen ist unter Schnitt (Intersection) abgeschlossen.  
Betrachte daher den Schnitt beider Mengen:

(AB)    (AB)=A    (BB)=A    =A.
\begin{aligned}
(A\cup B)\;\cap\;(A\cup\overline{B})
   &= A\;\cup\;(B\cap\overline{B}) \\
   &= A\;\cup\;\varnothing \\
   &= A .
\end{aligned}


Da beide Ausgangssprachen nach Annahme entscheidbar sind, wäre ihr Schnitt ebenfalls entscheidbar.  
Damit wäre AA entscheidbar – ein Widerspruch zur Voraussetzung, dass AA unentscheidbar ist.

Folglich kann nicht gleichzeitig gelten, dass ABA\cup B und ABA\cup\overline{B} entscheidbar sind.  
Damit ist garantiert, dass mindestens eine der beiden Sprachen unentscheidbar ist.

Die Aussage ist wahr.
\boxed{\text{Die Aussage ist wahr.}}

qwen/qwen3-235b-a22b

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Beweis durch Widerspruch:  
Angenommen, sowohl ABA \cup B als auch ABA \cup \overline{B} sind entscheidbar.  
1. Schnitt der Sprachen:  
   Der Schnitt (AB)(AB)(A \cup B) \cap (A \cup \overline{B}) ist gleich A(BB)=A=AA \cup (B \cap \overline{B}) = A \cup \emptyset = A.  
2. Abschlusseigenschaft:  
   Da entscheidbare Sprachen unter Durchschnitt abgeschlossen sind, folgt aus der Entscheidbarkeit von ABA \cup B und ABA \cup \overline{B} auch die Entscheidbarkeit von AA.  
3. Widerspruch:  
   Dies widerspricht der Voraussetzung, dass AA unentscheidbar ist.  
Fazit: Mindestens eine der Sprachen ABA \cup B oder ABA \cup \overline{B} muss unentscheidbar sein.

qwen/qwen3-235b-a22b-thinking-2507

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (0.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.
wrong answer for choice (1)

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Angenommen, sowohl ABA \cup B als auch ABA \cup \overline{B} wären entscheidbar. Da entscheidbare Sprachen unter Schnitt abgeschlossen sind, wäre auch die Sprache (AB)(AB)(A \cup B) \cap (A \cup \overline{B}) entscheidbar. Durch Anwendung des Distributivgesetzes gilt:
(AB)(AB)=A(BB)=A=A.
(A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) = A \cup \emptyset = A.

Dies impliziert, dass AA entscheidbar ist, was im Widerspruch zur Voraussetzung steht, dass AA unentscheidbar ist. Daher muss mindestens eine der Sprachen ABA \cup B oder ABA \cup \overline{B} unentscheidbar sein.

x-ai/grok-4

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Sei AΣA \subseteq \Sigma^* unentscheidbar und BΣB \subseteq \Sigma^* beliebig. Angenommen, sowohl C:=ABC := A \cup B als auch D:=ABD := A \cup \overline{B} sind entscheidbar. Dann ist auch CDC \cap D entscheidbar, da die entscheidbaren Sprachen unter Schnitt abgeschlossen sind. Es gilt jedoch
CD=(AB)(AB)=A(BB)=A=A.
C \cap D = (A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) = A \cup \emptyset = A.

Dies steht im Widerspruch zur Unentscheidbarkeit von AA. Also kann nicht CC und DD beide entscheidbar sein, d.h. mindestens eine der Sprachen ABA \cup B und ABA \cup \overline{B} ist unentscheidbar.

z-ai/glm-4.5

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma:=\{0,1\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (0.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L
wrong answer for choice (1)

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Die Aussage ist wahr. Wir beweisen dies durch Widerspruch.

Angenommen, beide Sprachen ABA \cup B und ABA \cup \overline{B} sind entscheidbar. Dann können wir einen Entscheider für AA konstruieren:

Für eine Eingabe wΣw \in \Sigma^*:
1. Prüfe, ob wABw \in A \cup B (entscheidbar nach Annahme)
2. Prüfe, ob wABw \in A \cup \overline{B} (entscheidbar nach Annahme)

Fallunterscheidung:
- Wenn wAw \in A, dann gilt wABw \in A \cup B und wABw \in A \cup \overline{B}.
- Wenn wAw \notin A, dann gilt wABw \in A \cup B genau dann, wenn wBw \in B, und wABw \in A \cup \overline{B} genau dann, wenn wBw \in \overline{B}.

Da BB und B\overline{B} eine Partition von Σ\Sigma^* bilden, gilt für wAw \notin A:
- Wenn wBw \in B, dann wABw \in A \cup B aber wABw \notin A \cup \overline{B}.
- Wenn wBw \notin B, dann wABw \notin A \cup B aber wABw \in A \cup \overline{B}.

Daraus folgt:
- Wenn wABw \in A \cup B und wABw \in A \cup \overline{B}, dann wAw \in A.
- Wenn ww in genau einer der beiden Mengen liegt, dann wAw \notin A.

Dies ergibt einen Entscheidungsalgorithmus für AA, was im Widerspruch zur Voraussetzung steht, dass AA unentscheidbar ist.

Daher muss mindestens eine der Sprachen ABA \cup B oder ABA \cup \overline{B} unentscheidbar sein.