Sprache welche albzählbar aber nicht aufzählbar ist?

Question

Wenn eine Sprache albzählbar, aber nicht aufzählbar ist, scheitert dies an dem nicht Vorhandensein eines berechenbaren Algorithmus, der die Elemente der Sprache in unendlicher Zeit aufzählen kann?

Answer 1

Hallo upmtz,

auch bei aufzählbaren Sprachen gibt es den Algorithmus

GdInfoII 5-12 ist die Definition von aufzählbaren Sprachen M *Teilmenge* E* heißt (rekursiv) aufzählbar genau dann, wenn es gibt eine surjektive, berechenbare Funktion f : IN_0 -> M gibt.

M heißt abzählbar gdw M injektiv in IN abbildbar ist. (GdInfoII 5-7)

Der unterschied ist also, dass es bei abzählbaren Sprachen auch injektiv ist (insgesamt also bijektiv) und bei aufzählbaren Sprachen nur surjektiv