www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Formale Sprachen" - Satz von Post
Satz von Post < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Satz von Post: Tipp
Status: (Frage) beantwortet Status 
Datum: 18:11 Fr 27.01.2012
Autor: judithlein

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

        
Bezug
Satz von Post: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Satz von Post: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:59 Sa 28.01.2012
Autor: judithlein


> > 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
>  


Bezug
                        
Bezug
Satz von Post: Antwort
Status: (Antwort) fertig Status 
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
> >  

>  


Bezug
                                
Bezug
Satz von Post: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:54 Mo 30.01.2012
Autor: judithlein


> > > > 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
> > >  

> >  

>  


Bezug
                                        
Bezug
Satz von Post: Antwort
Status: (Antwort) fertig Status 
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
> > > >  

> > >  

> >  

>  


Bezug
                                                
Bezug
Satz von Post: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!!!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de