VL-06 Rekursive Aufzählbarkeit

Question 1

Was ist der Unterschied zwischen einer entscheidbaren und einer semi-entscheidbaren Sprache?

Answer 1

Ein entscheidbare Sprache, hat eine TM, welche auf jedem Wort hält und alle Wörter akzeptiert, welche in der Sprache liegen.
Eine semi-entscheidbare Sprache, hat eine TM, welche alle Wörter akzeptiert die Teil der Sprache sind und keine Wörter die nicht Teil der Sprache sind. Im Gegensatz zu einer entscheidbaren Sprache, kann es sein, dass die TM nie terminiert für Wörter die nicht Teil der Sprache sind.

Question 2

Was ist ein Aufzähler und wie werden Sprachen genannt die einen Aufzähler besitzen?

Answer 2

Ein Aufzähler ist eine TM mit angeschlossenem Drucker, welcher alle Wörter ausdruckt, getrennt mit Trennzeichen, die Teil der Sprache sind.

Sprachen für die es einen Aufzähler gibt, werden rekursiv aufzählbar genannt

Question 3

Wie ist der Zusammenhang zwischen semi-entscheidbaren Sprachen und rekursiv aufzählbaren Sprachen?

Answer 3

Eine Sprache ist semi-entscheibar g.d.w. sie rekursiv aufzählbar ist

Question 4

Wie sind die Abschlusseigenschaften von semi-entscheidbaren Sprachen?

Answer 4

Semi-entscheidbare Sprachen sind unter Vereinigung und Durchnschnitt, nicht jedoch unter Komplement

Question 5

Was lässt sich bezüglich des Komplements von semi-entscheibaren Sprachen sagen?

Answer 5

Wenn eine Sprache und ihr Komplement semi-entscheibar sind, so ist die Sprache entscheidbar.

Question 6

Welche 4 Familien an Sprachen gibt es, bezüglich der Entscheidbarkeit?

Answer 6

1. Entscheidbare Sprachen
2. Semi-entscheidbare Sprachen
3. Sprachen mit semi-enscheidbaren Komplement
4. Sprache und Komplement sind unentscheidbar

Question 7

Wann ist eine Sprache L1 auf eine Sprache L2 reduzierbar?

Answer 7

Wenn es eine berechenbare Funktion f gibt, für die gilt:
x in L1 g.d.w. f(x) in L2

Question 8

Ist das totale Halteproblem entscheidbar?

Answer 8

Das totale Problem und sein Komplement ist nicht semi-entscheidbar