Main concepts

Question 1

Halteproblem

Answer 1

Entscheide ob ein Program mit einenr gegebenen Eingabe terminiert.

H = { _w | M halt auf w }

Question 2

Unterprogrammtechnik

Answer 2

Verwendet zum Beweis von Unetnscheidbarkeit.

• Sei L’ eine bereits analysierte und nicht -endscheidbare Sprache
• Sei L eine neue Sprache die wir untersuchen.

Um nachzuweisen, dass L nicht entscheidbar ist, genugt es zu zeigen, dass man mit Hilfe von Unterprogrammaufrufen einer TM M_L (zum Ent. von L) auch die Sprache L’ entscheiden kann.

Question 3

Diagonalisierung

Answer 3

Beweismethode die die eine Matrix mit Fokus auf die Diagonalspalte.

Question 4

Abzahlbarkeit

Answer 4

Menge abzahlbar wenn Menge leer oder wenn es eine surjektive Abbildung c: N -> M gibt.

Question 5

Semi-entscheidbarkeit

Answer 5

Wenn es 1 TM gibt die L erkennt.

L erkennt M, wenn:
M jedes wort aus L akzeptiert
M kein Wort akzeptiert, das nicht in L enthalten ist.

Question 6

Aufzahler

Answer 6

Variante der TM mit einem angeschlossenen Drucker. Eine BAnd funkzioniert als Ausgabeband auf dem sich der Kopf nur nach rechts bewegen kann und drauf nur geschrieben werden kann.

• Aufzahler mit leerem Arbeitsband gestartet und gibt mir der Zeit alle Worter in L auf dem Drucker aus.
• Die ausgegebenen Worter werden dabei immer durch ein Trennzeichen separiert, das nicht in Alphabet enthalten ist.
• Der Aufzahler druckt nur Worter in L.

Question 7

Rekursiv aufzahlbar

Answer 7

Wenn L einen Aufzahler hat