Leere Menge rekursiv aufzählbar ?
Florian Wittke
ich habe mich gefragt ob { } rekursiv aufzählbar ist?
Meiner Meinung nach nicht, denn wir haben definiert:
Eine Sprache L ist rekursiv aufzählbar, wenn es eine total berechenbare
Funktion
f:{0,1}* -> {0,1}* mit f({0,1}*) = L.
Es müßte also gelten: f:{0,1}* -> {0,1}* mit f({0,1}*) = {}.
Wenn der Definitionsbereich einer Funktion aber nicht leer ist, kann auch
der Bildbereich nicht leer sein, denn für jedes a im Definitionsbereich, ist
f(a) im Zielbereich. Folglich ex. eine solche Funktion nicht. Stimmt das so,
oder hab ich jetzt nen Wurm drin?
Hintergrund ist:
Ich möchte zeigen das Teilmengen von rekursiven zählbaren Sprechen, nicht
notwenigerweise aufzählbar sind. ({} ist ja Teilmenge jeder Menge).
gruß
florian
ronny herzog
Hallo!
Nach unserer Definition ist eine Sprache L r.a., wenn es eine TM M, die
auf Wörter dieser Sprache hält. -> Man kann doch ganz einfach eine
solche TM bauen, die prüft, ob das Eingabeband leer ist und hält, wenn
ja und in eine Endlossschleife geht, wenn nein.
Gruss, Ronny
Thomas Hühn
> Nach unserer Definition ist eine Sprache L r.a., wenn es eine TM M,
> die auf Wörter dieser Sprache hält. -> Man kann doch ganz einfach eine
> solche TM bauen, die prüft, ob das Eingabeband leer ist und hält, wenn
> ja und in eine Endlossschleife geht, wenn nein.
Dann hast du aber nicht die leere Menge, sondern die Sprache, die nur
aus dem leeren Wort besteht.
Thomas
Thomas Jansen
ronny herzog <ronny-...@web.de> writes:
> Florian Wittke wrote:
>> ich habe mich gefragt ob { } rekursiv aufzählbar ist?
>> Meiner Meinung nach nicht, denn wir haben definiert:
>> Eine Sprache L ist rekursiv aufzählbar, wenn es eine total berechenbare
>> Funktion
>> f:{0,1}* -> {0,1}* mit f({0,1}*) = L.
> Nach unserer Definition ist eine Sprache L r.a., wenn es eine TM M, die
> auf Wörter dieser Sprache hält.
Jetzt habe wir also zwei verschiedene Definitionen von r.a. Nach Florians
Definition ist \emptyset nicht r.a., wie Florian ja erläutert hat. Nach
Ronnys Definition ist \emtpyset r.a., weil eine nie haltende TM ja genau
auf den Wörtern auf \emptyset hält. Die Definitionen sind bezüglich
\emptyset also nicht äquivalent. Bezüglich aller anderen Sprachen sind sie
es aber schon, wie man sich überlegen kann - ich lasse die Details dann
jetzt mal als Übungsaufgabe ;-) Wegen der Sonderstellung von \emptyset ist
für Florians Fragestellung meiner Meinung nach Ronnyse Definition die
interessantere.
Thomas
--
Thomas Jansen
FB 4, LS 2, Univ. Dortmund, 44221 Dortmund, Germany
Thomas...@udo.edu http://ls2-www.cs.uni-dortmund.de/~jansen
Stephan Lehmke
> Hallo,
>
> ich habe mich gefragt ob { } rekursiv aufzählbar ist?
>
> Meiner Meinung nach nicht, denn wir haben definiert:
>
> Eine Sprache L ist rekursiv aufzählbar, wenn es eine total berechenbare
> Funktion
>
> f:{0,1}* -> {0,1}* mit f({0,1}*) = L.
>
>
> Es müßte also gelten: f:{0,1}* -> {0,1}* mit f({0,1}*) = {}.
Was heisst "total berechenbar"?
Dass f total ist? Dann ist das die Definition von "rekursive
Sprache". Fuer eine r.a. Sprache kann f partiell sein, und damit kann
die Wertmenge tatsaechlich leer sein.
Gruss
Stephan
Michael Hofmann
> ich habe mich gefragt ob { } rekursiv aufzählbar ist?
>
> Meiner Meinung nach nicht, denn wir haben definiert:
>
> Eine Sprache L ist rekursiv aufzählbar, wenn es eine total berechenbare
> Funktion
>
> f:{0,1}* -> {0,1}* mit f({0,1}*) = L.
im "Schoening" steht ungefaehr folgende Definition:
Eine Sprache A heisst rekursiv aufzaehlbar, falls A = {} oder falls es eine
totale und berechenbare ...
Per Definition ist A = {} also rekursiv aufzaehlbar (laut "Schoening"!).
MfG Michael
Holger Walliser
Michael Hofmann schrieb:
> Hallo,
[...]
>
> im "Schoening" steht ungefaehr folgende Definition:
>
> Eine Sprache A heisst rekursiv aufzaehlbar, falls A = {} oder falls es eine
> totale und berechenbare ...
>
> Per Definition ist A = {} also rekursiv aufzaehlbar (laut "Schoening"!).
>
> MfG Michael
Das ist wohl so auch eher Standard, da sich diese Definition dann mit den
anderen möglichen deckt!
Viele Grüße von
Holger
Matthias Bobzien
Also braucht man eine TM, die niemals anhält. Sowas sollte sehr leicht
zu konstruieren sein :-)
Diese TM akzeptiert kein Eingabewort, mithin ist die Menge der
akzeptierten Wörter leer. Damit ist dann die leere Menge nach obiger
Definition rekursiv aufzählbar.
Matthias
--
Matthias Bobzien
E-Mail: bob...@ikg.uni-bonn.de
Tjark Weber
> ich habe mich gefragt ob { } rekursiv aufzählbar ist?
Üblicherweise definiert man r.a. so, dass auch {} r.a. ist.
Andernfalls muss man bei Sätzen wie z.B. "Jede endliche Menge ist r.a." die
leere Menge immer als Sonderfall behandeln -- das will man eigentlich nicht.
> Meiner Meinung nach nicht, denn wir haben definiert:
>
> Eine Sprache L ist rekursiv aufzählbar, wenn es eine total berechenbare
> Funktion
>
> f:{0,1}* -> {0,1}* mit f({0,1}*) = L.
Nach "eurer" Definition ist {} also tatsächlich nicht r.a., wie du richtig
bemerkt hast.
> Hintergrund ist:
>
> Ich möchte zeigen das Teilmengen von rekursiven zählbaren Sprechen, nicht
> notwenigerweise aufzählbar sind. ({} ist ja Teilmenge jeder Menge).
Eine Übungsaufgabe? Dein Ansatz sollte volle Punktzahl bringen.
Ein anderer Ansatz, der auch funktioniert, wenn man {} als r.a. definiert
hat: Sei L eine Sprache über {0,1}, die nicht r.a. ist. (Eine solche Sprache
ist z.B. gegeben durch ... .) Offenbar ist L Teilmenge von {0,1}*. Zeige,
dass {0,1}* r.a. ist.
Freundliche Grüße,
Tjark
Nicolas Berr
> f:{0,1}* -> {0,1}* mit f({0,1}*) = L.
> Wenn der Definitionsbereich einer Funktion aber nicht leer ist, kann auch
> der Bildbereich nicht leer sein
Blöde Frage am Rande, wie ist denn {0,1}* definiert?
klingt irgendwie nach einer Potenzmenge...
ist dann nicht die Leere Menge nicht gleichsam Element dieser
Potenzmenge?
Demnach wäre der Definitionsbereich der Funtion nicht notwendigerweise
nicht leer...
... und der Bildbereich dann natürlich auch nicht ...
Prinzipiell stellt sich natürlich immer die philosophische Frage, ob man
"nichts" zählen kann. Weswegen in der Mathematik eben häufig die Leere
Menge explizit erwähnt wird.
Aber ich denke im Sinne des Begriffes Abzählbarkeit ist "nichts" immer
Abzählbar.
Gruß,
Nicolas
Marco Lange
> Blöde Frage am Rande, wie ist denn {0,1}* definiert?
> klingt irgendwie nach einer Potenzmenge...
> ist dann nicht die Leere Menge nicht gleichsam Element dieser
> Potenzmenge?
Gegeben sei ein Alphabet \Sigma. Dann kannst Du \Sigma^k einfach
mengentheorhetisch als kartesisches Produkt definieren, für
k \in \mathbb{N}_0.
Und \Sigma^{*} = \bigcup {i \in \mathbb{N}_0} \Sigma^k
{0,1}^{*} ist also die Menge aller endlichen (aber beliebig langen)
Folgen aus der Menge {0,1}.
Viele Grüße,
Marco