Satz von Post < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich habe eine Frage zum Satz von Post:
Eine Sprache A ist genau dann entscheidbar, wenn sowohl A als auch ihr Komplement [mm] E^{*} [/mm] \ A semi-entscheidbar sind.
Dieser Satz ist entscheidbar. Den Beweis habe ich auch verstanden. Allerdings soll er mir jetzt auch sagen, dass die rekursiv aufzählbaren Sprachen (also die Typ-0-Sprachen in der Chomsky-Hierarchie) unter dem Komplement nicht abgeschlossen sind. Ist das deswegen, weil gerade obiges entscheidbar ist, da es zwei verschiedene Turingmaschinen M für die Sprache A und M´ für die Sprache [mm] E^{*} [/mm] \ A gibt, die durch andere Turingmaschinen simuliert werden und diese ja entscheiden, ob das eingegebene Wort in der Sprache A oder in der Sprache [mm] E^{*} [/mm] \ A ist. Und da dies eben zwei verschiedene Maschinen sind, die verschiedene Sprachen verstehen sind die Sprachen offensichtlich nicht gleich und deswegen die rekursiv aufzählbaren Sprachen unter dem Komplement nicht abgeschlossen?
Ich hoffe man versteht was ich meine...
Und dann noch zu den zwei arten von charakteristischen Funktionen. Da gibt es ja die charakteristische Funktion, die eine 1 ausgibt, wenn das gegebene Wort in der Sprache A liegt oder eine 0 ausgibt wenn dies eben nicht Fall ist.
Die eingeschränkte charakteristische Funktion gibt im zweiten Fall garnichts aus und man sagt einfach "undefiniert".
Warum unterscheidet man überhaupt zwischen den Funktionen? Die machen doch beide im Prinzip das gleiche?
Danke schon mal!
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:14 Sa 28.01.2012 | | Autor: | sandp |
> Hallo,
>
> ich habe eine Frage zum Satz von Post:
>
> Eine Sprache A ist genau dann entscheidbar, wenn sowohl A
> als auch ihr Komplement [mm]E^{*}[/mm] \ A semi-entscheidbar sind.
>
> Dieser Satz ist entscheidbar. Den Beweis habe ich auch
> verstanden. Allerdings soll er mir jetzt auch sagen, dass
> die rekursiv aufzählbaren Sprachen (also die
> Typ-0-Sprachen in der Chomsky-Hierarchie) unter dem
> Komplement nicht abgeschlossen sind. Ist das deswegen, weil
> gerade obiges entscheidbar ist, da es zwei verschiedene
> Turingmaschinen M für die Sprache A und M´ für die
> Sprache [mm]E^{*}[/mm] \ A gibt, die durch andere Turingmaschinen
> simuliert werden und diese ja entscheiden, ob das
> eingegebene Wort in der Sprache A oder in der Sprache [mm]E^{*}[/mm]
> \ A ist. Und da dies eben zwei verschiedene Maschinen sind,
> die verschiedene Sprachen verstehen sind die Sprachen
> offensichtlich nicht gleich und deswegen die rekursiv
> aufzählbaren Sprachen unter dem Komplement nicht
> abgeschlossen?
> Ich hoffe man versteht was ich meine...
Ich hab jetzt nicht genau verstanden was du meinst, aber ich zeig dir mal ganz einfach warum das sofort folgt:
Gehen wir mal davon aus, dass die rekursiv aufzählbaren Sprachen unter Komplement abgeschlossen sind, überleg dir mal, was dann gelten würde?
>
> Und dann noch zu den zwei arten von charakteristischen
> Funktionen. Da gibt es ja die charakteristische Funktion,
> die eine 1 ausgibt, wenn das gegebene Wort in der Sprache A
> liegt oder eine 0 ausgibt wenn dies eben nicht Fall ist.
> Die eingeschränkte charakteristische Funktion gibt im
> zweiten Fall garnichts aus und man sagt einfach
> "undefiniert".
> Warum unterscheidet man überhaupt zwischen den
> Funktionen? Die machen doch beide im Prinzip das gleiche?
>
Stell dir die zwei charakteristische Funktionen als Turingmaschinene vor.
1. charakteristische Funktion: die Turingmaschine hält auf jeden Fall und gibt an ob das Wort in der Sprache ist oder nicht
2. charakteristische Funktion: die Turingmaschine hält nur wenn ein Wort in der Sprache liegt, falls das Wort nicht in der Sprache liegt, dann läuft die Turingmaschine unendlich lange
und das ist ja ein großer Unterschied
Gruß sandp
> Danke schon mal!
>
> Liebe Grüße
|
|
|
| |
|
> > Hallo,
> >
> > ich habe eine Frage zum Satz von Post:
> >
> > Eine Sprache A ist genau dann entscheidbar, wenn sowohl A
> > als auch ihr Komplement [mm]E^{*}[/mm] \ A semi-entscheidbar sind.
> >
> > Dieser Satz ist entscheidbar. Den Beweis habe ich auch
> > verstanden. Allerdings soll er mir jetzt auch sagen, dass
> > die rekursiv aufzählbaren Sprachen (also die
> > Typ-0-Sprachen in der Chomsky-Hierarchie) unter dem
> > Komplement nicht abgeschlossen sind. Ist das deswegen, weil
> > gerade obiges entscheidbar ist, da es zwei verschiedene
> > Turingmaschinen M für die Sprache A und M´ für die
> > Sprache [mm]E^{*}[/mm] \ A gibt, die durch andere Turingmaschinen
> > simuliert werden und diese ja entscheiden, ob das
> > eingegebene Wort in der Sprache A oder in der Sprache [mm]E^{*}[/mm]
> > \ A ist. Und da dies eben zwei verschiedene Maschinen sind,
> > die verschiedene Sprachen verstehen sind die Sprachen
> > offensichtlich nicht gleich und deswegen die rekursiv
> > aufzählbaren Sprachen unter dem Komplement nicht
> > abgeschlossen?
> > Ich hoffe man versteht was ich meine...
>
> Ich hab jetzt nicht genau verstanden was du meinst, aber
> ich zeig dir mal ganz einfach warum das sofort folgt:
> Gehen wir mal davon aus, dass die rekursiv aufzählbaren
> Sprachen unter Komplement abgeschlossen sind, überleg dir
> mal, was dann gelten würde?
>
Dann gäbe es eine Turingmaschine die beide Sprachen akzeptiert. Das ist ja an sich schon wiedersprüchlich, oder? Denn eine Turingmaschine kann entweder die eine oder die andere Sprache akzeptieren. Oder denke ich falsch?
> >
> > Und dann noch zu den zwei arten von charakteristischen
> > Funktionen. Da gibt es ja die charakteristische Funktion,
> > die eine 1 ausgibt, wenn das gegebene Wort in der Sprache A
> > liegt oder eine 0 ausgibt wenn dies eben nicht Fall ist.
> > Die eingeschränkte charakteristische Funktion gibt im
> > zweiten Fall garnichts aus und man sagt einfach
> > "undefiniert".
> > Warum unterscheidet man überhaupt zwischen den
> > Funktionen? Die machen doch beide im Prinzip das gleiche?
> >
> Stell dir die zwei charakteristische Funktionen als
> Turingmaschinene vor.
> 1. charakteristische Funktion: die Turingmaschine hält
> auf jeden Fall und gibt an ob das Wort in der Sprache ist
> oder nicht
> 2. charakteristische Funktion: die Turingmaschine hält
> nur wenn ein Wort in der Sprache liegt, falls das Wort
> nicht in der Sprache liegt, dann läuft die Turingmaschine
> unendlich lange
>
> und das ist ja ein großer Unterschied
>
Das stimmt schon. Aber im Prinzip geben mir dann doch beide an ob ein Wort in der Sprache enthalten ist oder nicht. Nur im zweiten Fall weiß man eventuell nicht, ob die Maschine gerade nur noch etwas Zeit braucht oder ob das Wort einfach nicht in der Sprache enthalten ist.
> Gruß sandp
>
> > Danke schon mal!
> >
> > Liebe Grüße
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:01 So 29.01.2012 | | Autor: | sandp |
> > > Hallo,
> > >
> > > ich habe eine Frage zum Satz von Post:
> > >
> > > Eine Sprache A ist genau dann entscheidbar, wenn sowohl A
> > > als auch ihr Komplement [mm]E^{*}[/mm] \ A semi-entscheidbar sind.
> > >
> > > Dieser Satz ist entscheidbar. Den Beweis habe ich auch
> > > verstanden. Allerdings soll er mir jetzt auch sagen, dass
> > > die rekursiv aufzählbaren Sprachen (also die
> > > Typ-0-Sprachen in der Chomsky-Hierarchie) unter dem
> > > Komplement nicht abgeschlossen sind. Ist das deswegen, weil
> > > gerade obiges entscheidbar ist, da es zwei verschiedene
> > > Turingmaschinen M für die Sprache A und M´ für die
> > > Sprache [mm]E^{*}[/mm] \ A gibt, die durch andere Turingmaschinen
> > > simuliert werden und diese ja entscheiden, ob das
> > > eingegebene Wort in der Sprache A oder in der Sprache [mm]E^{*}[/mm]
> > > \ A ist. Und da dies eben zwei verschiedene Maschinen sind,
> > > die verschiedene Sprachen verstehen sind die Sprachen
> > > offensichtlich nicht gleich und deswegen die rekursiv
> > > aufzählbaren Sprachen unter dem Komplement nicht
> > > abgeschlossen?
> > > Ich hoffe man versteht was ich meine...
> >
> > Ich hab jetzt nicht genau verstanden was du meinst, aber
> > ich zeig dir mal ganz einfach warum das sofort folgt:
> > Gehen wir mal davon aus, dass die rekursiv
> aufzählbaren
> > Sprachen unter Komplement abgeschlossen sind, überleg dir
> > mal, was dann gelten würde?
> >
> Dann gäbe es eine Turingmaschine die beide Sprachen
> akzeptiert. Das ist ja an sich schon wiedersprüchlich,
> oder? Denn eine Turingmaschine kann entweder die eine oder
> die andere Sprache akzeptieren. Oder denke ich falsch?
viel einfacher, wenn die rekursiv aufzählbaren Sprachen unter Komplement abgeschlossen wären, dann würde der Satz von Post immer gelten, damit wäre jede rekursiv aufzählbare Sprache eine rekursive Sprache und das ist offensichtlich ein Widerspruch
>
> > >
> > > Und dann noch zu den zwei arten von charakteristischen
> > > Funktionen. Da gibt es ja die charakteristische Funktion,
> > > die eine 1 ausgibt, wenn das gegebene Wort in der Sprache A
> > > liegt oder eine 0 ausgibt wenn dies eben nicht Fall ist.
> > > Die eingeschränkte charakteristische Funktion gibt im
> > > zweiten Fall garnichts aus und man sagt einfach
> > > "undefiniert".
> > > Warum unterscheidet man überhaupt zwischen den
> > > Funktionen? Die machen doch beide im Prinzip das gleiche?
> > >
> > Stell dir die zwei charakteristische Funktionen als
> > Turingmaschinene vor.
> > 1. charakteristische Funktion: die Turingmaschine hält
> > auf jeden Fall und gibt an ob das Wort in der Sprache ist
> > oder nicht
> > 2. charakteristische Funktion: die Turingmaschine hält
> > nur wenn ein Wort in der Sprache liegt, falls das Wort
> > nicht in der Sprache liegt, dann läuft die Turingmaschine
> > unendlich lange
> >
> > und das ist ja ein großer Unterschied
> >
>
> Das stimmt schon. Aber im Prinzip geben mir dann doch beide
> an ob ein Wort in der Sprache enthalten ist oder nicht. Nur
> im zweiten Fall weiß man eventuell nicht, ob die Maschine
> gerade nur noch etwas Zeit braucht oder ob das Wort einfach
> nicht in der Sprache enthalten ist.
>
> > Gruß sandp
Die zweite TM kann dir eben das nicht angeben, sie läuft unter umständen unendlich lange, weil das Wort nicht in der Sprache ist. Aber du kannst nie eine Aussage treffen, weil du nicht weißt ob die TM doch noch irgendwann hält und JA ausgibt.
> >
> > > Danke schon mal!
> > >
> > > Liebe Grüße
> >
>
|
|
|
| |
|
> > > > Hallo,
> > > >
> > > > ich habe eine Frage zum Satz von Post:
> > > >
> > > > Eine Sprache A ist genau dann entscheidbar, wenn sowohl A
> > > > als auch ihr Komplement [mm]E^{*}[/mm] \ A semi-entscheidbar sind.
> > > >
> > > > Dieser Satz ist entscheidbar. Den Beweis habe ich auch
> > > > verstanden. Allerdings soll er mir jetzt auch sagen, dass
> > > > die rekursiv aufzählbaren Sprachen (also die
> > > > Typ-0-Sprachen in der Chomsky-Hierarchie) unter dem
> > > > Komplement nicht abgeschlossen sind. Ist das deswegen, weil
> > > > gerade obiges entscheidbar ist, da es zwei verschiedene
> > > > Turingmaschinen M für die Sprache A und M´ für die
> > > > Sprache [mm]E^{*}[/mm] \ A gibt, die durch andere Turingmaschinen
> > > > simuliert werden und diese ja entscheiden, ob das
> > > > eingegebene Wort in der Sprache A oder in der Sprache [mm]E^{*}[/mm]
> > > > \ A ist. Und da dies eben zwei verschiedene Maschinen sind,
> > > > die verschiedene Sprachen verstehen sind die Sprachen
> > > > offensichtlich nicht gleich und deswegen die rekursiv
> > > > aufzählbaren Sprachen unter dem Komplement nicht
> > > > abgeschlossen?
> > > > Ich hoffe man versteht was ich meine...
> > >
> > > Ich hab jetzt nicht genau verstanden was du meinst, aber
> > > ich zeig dir mal ganz einfach warum das sofort folgt:
> > > Gehen wir mal davon aus, dass die rekursiv
> > aufzählbaren
> > > Sprachen unter Komplement abgeschlossen sind, überleg dir
> > > mal, was dann gelten würde?
> > >
> > Dann gäbe es eine Turingmaschine die beide Sprachen
> > akzeptiert. Das ist ja an sich schon wiedersprüchlich,
> > oder? Denn eine Turingmaschine kann entweder die eine oder
> > die andere Sprache akzeptieren. Oder denke ich falsch?
>
> viel einfacher, wenn die rekursiv aufzählbaren Sprachen
> unter Komplement abgeschlossen wären, dann würde der Satz
> von Post immer gelten, damit wäre jede rekursiv
> aufzählbare Sprache eine rekursive Sprache und das ist
> offensichtlich ein Widerspruch
> >
Ok...ich glaube ich habe es verstanden. Der einzige Unterschied zwischen rekursiven und rekursiv-aufzählbaren Sprachen ist doch nur, dass eine Turingmaschine bei den rekursiven Sprachen halten muss und bei den rekursiv-aufzählbaren Sprachen nicht unbedingt, oder gibt es da sonst noch etwas zu beachten?
> > > >
> > > > Und dann noch zu den zwei arten von charakteristischen
> > > > Funktionen. Da gibt es ja die charakteristische Funktion,
> > > > die eine 1 ausgibt, wenn das gegebene Wort in der Sprache A
> > > > liegt oder eine 0 ausgibt wenn dies eben nicht Fall ist.
> > > > Die eingeschränkte charakteristische Funktion gibt im
> > > > zweiten Fall garnichts aus und man sagt einfach
> > > > "undefiniert".
> > > > Warum unterscheidet man überhaupt zwischen den
> > > > Funktionen? Die machen doch beide im Prinzip das gleiche?
> > > >
> > > Stell dir die zwei charakteristische Funktionen als
> > > Turingmaschinene vor.
> > > 1. charakteristische Funktion: die Turingmaschine
> hält
> > > auf jeden Fall und gibt an ob das Wort in der Sprache ist
> > > oder nicht
> > > 2. charakteristische Funktion: die Turingmaschine
> hält
> > > nur wenn ein Wort in der Sprache liegt, falls das Wort
> > > nicht in der Sprache liegt, dann läuft die Turingmaschine
> > > unendlich lange
> > >
> > > und das ist ja ein großer Unterschied
> > >
> >
> > Das stimmt schon. Aber im Prinzip geben mir dann doch beide
> > an ob ein Wort in der Sprache enthalten ist oder nicht. Nur
> > im zweiten Fall weiß man eventuell nicht, ob die Maschine
> > gerade nur noch etwas Zeit braucht oder ob das Wort einfach
> > nicht in der Sprache enthalten ist.
> >
> > > Gruß sandp
>
> Die zweite TM kann dir eben das nicht angeben, sie läuft
> unter umständen unendlich lange, weil das Wort nicht in
> der Sprache ist. Aber du kannst nie eine Aussage treffen,
> weil du nicht weißt ob die TM doch noch irgendwann hält
> und JA ausgibt.
> > >
> > > > Danke schon mal!
> > > >
> > > > Liebe Grüße
> > >
> >
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:52 Mo 30.01.2012 | | Autor: | sandp |
> > > > > Hallo,
> > > > >
> > > > > ich habe eine Frage zum Satz von Post:
> > > > >
> > > > > Eine Sprache A ist genau dann entscheidbar, wenn sowohl A
> > > > > als auch ihr Komplement [mm]E^{*}[/mm] \ A semi-entscheidbar sind.
> > > > >
> > > > > Dieser Satz ist entscheidbar. Den Beweis habe ich auch
> > > > > verstanden. Allerdings soll er mir jetzt auch sagen, dass
> > > > > die rekursiv aufzählbaren Sprachen (also die
> > > > > Typ-0-Sprachen in der Chomsky-Hierarchie) unter dem
> > > > > Komplement nicht abgeschlossen sind. Ist das deswegen, weil
> > > > > gerade obiges entscheidbar ist, da es zwei verschiedene
> > > > > Turingmaschinen M für die Sprache A und M´ für die
> > > > > Sprache [mm]E^{*}[/mm] \ A gibt, die durch andere Turingmaschinen
> > > > > simuliert werden und diese ja entscheiden, ob das
> > > > > eingegebene Wort in der Sprache A oder in der Sprache [mm]E^{*}[/mm]
> > > > > \ A ist. Und da dies eben zwei verschiedene Maschinen sind,
> > > > > die verschiedene Sprachen verstehen sind die Sprachen
> > > > > offensichtlich nicht gleich und deswegen die rekursiv
> > > > > aufzählbaren Sprachen unter dem Komplement nicht
> > > > > abgeschlossen?
> > > > > Ich hoffe man versteht was ich meine...
> > > >
> > > > Ich hab jetzt nicht genau verstanden was du meinst, aber
> > > > ich zeig dir mal ganz einfach warum das sofort folgt:
> > > > Gehen wir mal davon aus, dass die rekursiv
> > > aufzählbaren
> > > > Sprachen unter Komplement abgeschlossen sind, überleg dir
> > > > mal, was dann gelten würde?
> > > >
> > > Dann gäbe es eine Turingmaschine die beide Sprachen
> > > akzeptiert. Das ist ja an sich schon wiedersprüchlich,
> > > oder? Denn eine Turingmaschine kann entweder die eine oder
> > > die andere Sprache akzeptieren. Oder denke ich falsch?
> >
> > viel einfacher, wenn die rekursiv aufzählbaren Sprachen
> > unter Komplement abgeschlossen wären, dann würde der Satz
> > von Post immer gelten, damit wäre jede rekursiv
> > aufzählbare Sprache eine rekursive Sprache und das ist
> > offensichtlich ein Widerspruch
> > >
> Ok...ich glaube ich habe es verstanden. Der einzige
> Unterschied zwischen rekursiven und rekursiv-aufzählbaren
> Sprachen ist doch nur, dass eine Turingmaschine bei den
> rekursiven Sprachen halten muss und bei den
> rekursiv-aufzählbaren Sprachen nicht unbedingt, oder gibt
> es da sonst noch etwas zu beachten?
>
genau entspricht ja deinen charakteristischen Funktionen
> > > > >
> > > > > Und dann noch zu den zwei arten von charakteristischen
> > > > > Funktionen. Da gibt es ja die charakteristische Funktion,
> > > > > die eine 1 ausgibt, wenn das gegebene Wort in der Sprache A
> > > > > liegt oder eine 0 ausgibt wenn dies eben nicht Fall ist.
> > > > > Die eingeschränkte charakteristische Funktion gibt im
> > > > > zweiten Fall garnichts aus und man sagt einfach
> > > > > "undefiniert".
> > > > > Warum unterscheidet man überhaupt zwischen
> den
> > > > > Funktionen? Die machen doch beide im Prinzip das gleiche?
> > > > >
> > > > Stell dir die zwei charakteristische Funktionen als
> > > > Turingmaschinene vor.
> > > > 1. charakteristische Funktion: die Turingmaschine
> > hält
> > > > auf jeden Fall und gibt an ob das Wort in der Sprache ist
> > > > oder nicht
> > > > 2. charakteristische Funktion: die Turingmaschine
> > hält
> > > > nur wenn ein Wort in der Sprache liegt, falls das Wort
> > > > nicht in der Sprache liegt, dann läuft die Turingmaschine
> > > > unendlich lange
> > > >
> > > > und das ist ja ein großer Unterschied
> > > >
> > >
> > > Das stimmt schon. Aber im Prinzip geben mir dann doch beide
> > > an ob ein Wort in der Sprache enthalten ist oder nicht. Nur
> > > im zweiten Fall weiß man eventuell nicht, ob die Maschine
> > > gerade nur noch etwas Zeit braucht oder ob das Wort einfach
> > > nicht in der Sprache enthalten ist.
> > >
> > > > Gruß sandp
> >
> > Die zweite TM kann dir eben das nicht angeben, sie läuft
> > unter umständen unendlich lange, weil das Wort nicht in
> > der Sprache ist. Aber du kannst nie eine Aussage treffen,
> > weil du nicht weißt ob die TM doch noch irgendwann hält
> > und JA ausgibt.
> > > >
> > > > > Danke schon mal!
> > > > >
> > > > > Liebe Grüße
> > > >
> > >
> >
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:57 Mo 30.01.2012 | | Autor: | judithlein |
Ok, dann denke ich ich habe es verstanden. Ansonsten darf ich mich hoffentlich noch mal melden :) Vielen Dank!!!
|
|
|
|
