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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Beweis:

Wir zeigen die Aussage durch Widerspruch.

Annahme: Beide Sprachen A∪BA \cup B und A∪B‾A \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:
(A∪B)∩(A∪B‾)(A \cup B) \cap (A \cup \overline{B})

Nach den Distributivgesetzen der Mengenlehre gilt:
(A∪B)∩(A∪B‾)=A∪(B∩B‾)=A∪∅=A(A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) = A \cup \emptyset = A

Das bedeutet: Wenn sowohl A∪BA \cup B als auch A∪B‾A \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 A∪BA \cup B oder A∪B‾A \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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Angenommen, sowohl A∪BA \cup B als auch A∪B‾A \cup \overline{B} sind entscheidbar. Da entscheidbare Sprachen unter Schnitt abgeschlossen sind, ist auch (A∪B)∩(A∪B‾)(A \cup B) \cap (A \cup \overline{B}) entscheidbar. Es gilt:
(A∪B)∩(A∪B‾)=A∪(B∩B‾)=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 A∪BA \cup B oder A∪B‾A \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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Die Aussage ist wahr. Wir beweisen dies durch Widerspruch.

Angenommen, sowohl A∪BA \cup B als auch A∪B‾A \cup \overline{B} sind entscheidbar. Dann gilt:
A=(A∪B)∩(A∪B‾).
A = (A \cup B) \cap (A \cup \overline{B}).

Begründung:
- Ist x∈Ax \in A, so ist x∈A∪Bx \in A \cup B und x∈A∪B‾x \in A \cup \overline{B}, also x∈(A∪B)∩(A∪B‾)x \in (A \cup B) \cap (A \cup \overline{B}).
- Ist x∈(A∪B)∩(A∪B‾)x \in (A \cup B) \cap (A \cup \overline{B}), so folgt:  
  Wäre x∉Ax \notin A, dann müsste x∈Bx \in B (aus x∈A∪Bx \in A \cup B) und x∈B‾x \in \overline{B} (aus x∈A∪B‾x \in A \cup \overline{B}) gelten, was unmöglich ist. Also ist x∈Ax \in A.

Da die entscheidbaren Sprachen unter Schnitt abgeschlossen sind, ist (A∪B)∩(A∪B‾)(A \cup B) \cap (A \cup \overline{B}) entscheidbar. Somit wäre AA entscheidbar, im Widerspruch zur Voraussetzung. Daher muss mindestens eine der Sprachen A∪BA \cup B oder A∪B‾A \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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
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 A∪BA \cup B als auch A∪B‾A \cup \overline{B} entscheidbar sind.

Seien L1=A∪BL_1 = A \cup B und L2=A∪B‾L_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 L1∩L2L_1 \cap L_2 entscheidbar.

Betrachten wir nun die Menge L1∩L2L_1 \cap L_2. Mithilfe der Distributivgesetze der Mengenlehre können wir den Ausdruck vereinfachen:
L1∩L2=(A∪B)∩(A∪B‾)=A∪(B∩B‾) 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. B∩B‾=∅B \cap \overline{B} = \emptyset.
Somit gilt:
L1∩L2=A∪∅=A L_1 \cap L_2 = A \cup \emptyset = A 
Wir haben also gezeigt, dass die Sprache AA identisch ist mit der Sprache L1∩L2L_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 A∪BA \cup B als auch A∪B‾A \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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Beweis: Angenommen, sowohl A∪BA \cup B als auch A∪B‾A \cup \overline{B} seien entscheidbar. Dann ist auch ihr Durchschnitt entscheidbar. Es gilt
(A∪B)∩(A∪B‾)  =  A∪(B∩B‾)  =  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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
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  

A∪BundA∪B‾
A\cup B \qquad\text{und}\qquad A\cup\overline{B}


entscheidbar sind.

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

(A∪B)  ∩  (A∪B‾)=A  ∪  (B∩B‾)=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 A∪BA\cup B und A∪B‾A\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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Beweis durch Widerspruch:  
Angenommen, sowohl A∪BA \cup B als auch A∪B‾A \cup \overline{B} sind entscheidbar.  
1. Schnitt der Sprachen:  
   Der Schnitt (A∪B)∩(A∪B‾)(A \cup B) \cap (A \cup \overline{B}) ist gleich A∪(B∩B‾)=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 A∪BA \cup B und A∪B‾A \cup \overline{B} auch die Entscheidbarkeit von AA.  
3. Widerspruch:  
   Dies widerspricht der Voraussetzung, dass AA unentscheidbar ist.  
Fazit: Mindestens eine der Sprachen A∪BA \cup B oder A∪B‾A \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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.
wrong answer for choice (1)

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Angenommen, sowohl A∪BA \cup B als auch A∪B‾A \cup \overline{B} wären entscheidbar. Da entscheidbare Sprachen unter Schnitt abgeschlossen sind, wäre auch die Sprache (A∪B)∩(A∪B‾)(A \cup B) \cap (A \cup \overline{B}) entscheidbar. Durch Anwendung des Distributivgesetzes gilt:
(A∪B)∩(A∪B‾)=A∪(B∩B‾)=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 A∪BA \cup B oder A∪B‾A \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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Sei A⊆Σ∗A \subseteq \Sigma^* unentscheidbar und B⊆Σ∗B \subseteq \Sigma^* beliebig. Angenommen, sowohl C:=A∪BC := A \cup B als auch D:=A∪B‾D := A \cup \overline{B} sind entscheidbar. Dann ist auch C∩DC \cap D entscheidbar, da die entscheidbaren Sprachen unter Schnitt abgeschlossen sind. Es gilt jedoch
C∩D=(A∪B)∩(A∪B‾)=A∪(B∩B‾)=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 A∪BA \cup B und A∪B‾A \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 unentscheidbar☒LaL^a ist unentscheidbar☐Es 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?
☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.
☒Wahr☐Falsch
Die Aussage ist wahr. Wir beweisen dies durch Widerspruch.

Angenommen, beide Sprachen A∪BA \cup B und A∪B‾A \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 w∈A∪Bw \in A \cup B (entscheidbar nach Annahme)
2. Prüfe, ob w∈A∪B‾w \in A \cup \overline{B} (entscheidbar nach Annahme)

Fallunterscheidung:
- Wenn w∈Aw \in A, dann gilt w∈A∪Bw \in A \cup B und w∈A∪B‾w \in A \cup \overline{B}.
- Wenn w∉Aw \notin A, dann gilt w∈A∪Bw \in A \cup B genau dann, wenn w∈Bw \in B, und w∈A∪B‾w \in A \cup \overline{B} genau dann, wenn w∈B‾w \in \overline{B}.

Da BB und B‾\overline{B} eine Partition von Σ∗\Sigma^* bilden, gilt für w∉Aw \notin A:
- Wenn w∈Bw \in B, dann w∈A∪Bw \in A \cup B aber w∉A∪B‾w \notin A \cup \overline{B}.
- Wenn w∉Bw \notin B, dann w∉A∪Bw \notin A \cup B aber w∈A∪B‾w \in A \cup \overline{B}.

Daraus folgt:
- Wenn w∈A∪Bw \in A \cup B und w∈A∪B‾w \in A \cup \overline{B}, dann w∈Aw \in A.
- Wenn ww in genau einer der beiden Mengen liegt, dann w∉Aw \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 A∪BA \cup B oder A∪B‾A \cup \overline{B} unentscheidbar sein.