Lemmas/Satze/Abschlusseigenschaften

Question 1

Satz von Rice

Answer 1

Sei R die Menge der von TMen berechenbaren partiellen Funktionen.

NullMenge in S in R mit S isnt NullMenge und S isnt R.

Dann die Sprache of S ( L(S) ) ist unentscheidbar.

Question 2

Abschlusseigenschaften von Ent. Sprachen?

Answer 2

Sprache L entscheidbar => Komplement entscheidbar

Vereinigung

Durchschnitt

Question 3

Abschlusseigenschaften von unent. Sprachen:

Answer 3

Vereinigung und Durchschnitt

Question 4

L und Komplement von L rekursiv aufzahlbar dann …

Answer 4

L entshceidbar

Question 5

Berechenbarkeitslandschaft:

Answer 5

1) L ent, und L und Kompl. L rekursiv aufzahlbar
2) L rek. auf., aber Kompl. L nicht rek auf.
3) Kompl. L rek. auf., aber L nicht rek auf.
4) L und Kompl. L nicht rek. auf.

Question 6

L1 <= L2 und L2 rek. auf. => …

Answer 6

L1 rek. auf.

Question 7

L1 <= L2 und L1 nicht rek. auf. => …

Answer 7

L2 nicht rek. auf.

Question 8

Totales Halteproblem und Komplement von Totales Halteproblem sind …(aufzahlbar oder nicht)

Answer 8

nicht rek. auf.

Question 9

PCP ent oder unent.?

Answer 9

Unent. geklart fur mehr als 4 Dominos, fur 3-4 Dominos Entscheidbarkeit ungeklart, fur 1,2 ent.

Question 10

Reduktion von H und MPCP

Answer 10

H<=MPCP

Question 11

Reduktion von MPCP und PCP

Answer 11

MPCP <= PCP