Semi-Entscheidbarkeit & Rekursive Aufzählbarkeit

Question 1

M erkennt L, wenn…

Answer 1

M jedes Wort aus L akzeptiert und kein Wort akzeptiert, das nicht in L enthalten ist.

Question 2

L heißt semi-entscheidbar, wenn…

Answer 2

eine TM existiert, die die Sprache L erkennt.

Question 3

Das Halteproblem ist… (entscheidbar/nicht entscheidbar/semi-entscheidbar)

Answer 3

nicht entscheidbar, aber semi-entscheidbar.

Question 4

Definition: Ein Aufzähler für eine Sprache L⊆Σ* ist…

Answer 4

eine Variante der TM mit einem angeschlossenen Drucker.

Question 5

Der Drucker des Aufzählers ist..

Answer 5

ein zusätzliches Ausgabeband, auf dem sich der Kopf nur nach rechts bewegen kann und auf dem nur geschrieben wird.

Question 6

Ein Aufzähler funktioniert so:

Answer 6

• wird mit dem leerem Arbeitsband gestartet und gibt mit der Zeit alle Wörter in L auf dem Drucker aus
• Die ausgegebene Wörter immer durch ein Trennzeichen separiert, das nicht in Σ enthalten ist
• Der Aufzähler druckt ausschliesslich Wörter in L.

Question 7

Definition: Wenn es für L einen Aufzähler gibt, so heißt L…

Answer 7

rekursiv aufzählbar.

Question 8

L ist rekursiv aufzählbar genau dann, wenn L … ist.

Answer 8

semi-entscheidbar

Question 9

Durchschnitt: Wenn L1 und L2 entscheidbar, dann L1 ∩ L2 ist …

Answer 9

entscheidbar

Question 10

Durchschnitt: Wenn L1 und L2 rekursiv aufzählbar, dann L1 ∩ L2 ist…

Answer 10

rekursiv aufzählbar

Question 11

Vereinigung: Wenn L1 und L2 entscheidbar, dann L1 ∪ L2 ist …

Answer 11

entscheidbar

Question 12

Wenn L1 und L2 rekursiv aufzählbar, dann L1 ∪ L2 ist …

Answer 12

rekursiv aufzählbar

Question 13

Wenn sowohl L⊆Σ* als auch ihr Komplement not L := Σ* \ L rekursiv aufzählbar, so ist L …

Answer 13

entscheidbar

Question 14

Wenn L entscheidbar, ihr Komplement not L ist..

Answer 14

entscheidbar

Question 15

Wenn L rekursiv aufzählbar, ihr Komplement not L ist nicht unbedingt..

Answer 15

rekursiv aufzählbar

Question 16

Graphzusammenhang, Hamiltonkreis sind … Sprachen, wobei L … und not L ist ….

Answer 16

entscheidbare, rekursiv aufzählbar, rekursiv aufzählbar

Question 17

Beispiele von entscheidbare Sprachen, wo sowohl L als auch not L rekursiv aufzählbar

Answer 17

Graphzusammenhang, Hamiltonkreis

Question 18

H, H_epsilon, not D sind… Sprachen, mit ….. Komplement

Answer 18

rekursiv aufzählbar, nicht rekursiv aufzählbarem

Question 19

not H, not H_epsilon, D sind… Sprachen, mit ….. Komplement

Answer 19

nicht rekursiv aufzählbare, rekursiv aufzählbarem

Question 20

Beispiele von rekursiv aufzählbar Sprachen mit nicht rekursiv aufzählbarem Komplement

Answer 20

H, H_epsilon, not D

Question 21

Beispiele von nicht rekursiv aufzählbar Sprachen mit rekursiv aufzählbarem Komplement

Answer 21

not H, not H_epsilon, D

Question 22

Unentscheidbare Sprachen mit unentscheidbarem Komplement

Answer 22

H_tot, not H_tot

Question 23

H_tot ist eine … Sprache mit … Komplement

Answer 23

nicht rekursiv (aufzählbare), nicht rekursiv (aufzählbarem)

Question 24

Definition Reduktion zweier Sprachen

Answer 24

Seien L1 und L2 zwei Sprachen über einem Alphabet Σ. Dann heißt L1 auf L2 reduzierbar, wenn es eine berechenbare Funktion f : Σ* -> Σ* existiert, so dass für alle x ϵ Σ* gilt: x ϵ L1 <=> f(x) ϵ L2

Question 25

Seien L1 und L2 zwei Sprachen über einem Alphabet Σ. Wenn es eine berechenbare Funktion f : Σ* -> Σ* existiert, so dass für alle x ϵ Σ* gilt: x ϵ L1 <=> f(x) ϵ L2 gilt, dann ist L1 auf L2 ....

Answer 25

reduzierbar

Question 26

Definition Reduktion

Answer 26

Ein Algorithmus, der die Instanzen eines Startproblems als Spezialfälle eines Zielproblems formuliert.

Question 27

Wenn L1 ≤ L2 und L2 rekursiv aufzählbar, so ist L1...

Answer 27

rekursiv aufzählbar

Question 28

Wenn L1 ≤ L2 und L1 nicht rekursiv aufzählbar, so ist L2...

Answer 28

nicht rekursiv aufzählbar

Question 29

Definition Totales Halteproblem

Answer 29

{Gödelnummer von M | M hält auf jeder Eingabe}

Question 30

Wenn eine Sprache ist unentscheidbar, aber rekursiv aufzählbar, dann ihr Komplement ist...

Answer 30

nicht rekursiv aufzählbar

Question 31

Htot ist...

Answer 31

nicht rekursiv aufzählbar

Question 32

Not Htot ist...

Answer 32

nicht rekursiv aufzählbar

Question 33

Aus A ≤ not A folgt dass...

Answer 33

Not A ≤ A

Question 34

Wenn L1 ≤ L2 und L2 entscheidbar, dann ist L1...

Answer 34

L1 entscheidbar

Question 35

Wenn L1 ≤ L2 und L1 nicht entscheidbar, dann L2 ist...

Answer 35

Nicht entscheidbar