Die Mathe-Redaktion - 24.08.2019 16:13 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 445 Gäste und 25 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Definition Trivialität von Indexmengen (wie im Satz von Rice)
Druckversion
Druckversion
Autor
Universität/Hochschule J Definition Trivialität von Indexmengen (wie im Satz von Rice)
egf
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2008
Mitteilungen: 551
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-19


Hallo Bilbo (und natürlich auch Andere)

Ich beziehe mich auf den Thread:
Sind folgende Sprachen entscheidbar? (u.a. Satz von Rice)

2019-07-19 10:02 - Bilbo in Beitrag No. 4 schreibt:
@egf:
2019-07-18 15:04 - egf in Beitrag No. 2 schreibt:
Es ginge mir um die Klammer: "eine, die nie hält": Das wäre mMn nicht zulässig, denn eine Solche erkennt ja gar keine Sprache, resp. dann wäre ja jede Sprache nicht-trivial.
Nein, das stimmt so nicht. Trivialität ist ja eine Eigenschaft einer Indexmenge, also einer Menge von Maschinenkodierungen. Und Nichttrivialität bedeutet in diesem Zusammenhang nur, dass es mindestens eine Maschine gibt, deren Kodierung in dieser Menge enthalten ist und mindestens eine, deren Kodierung nicht darin enthalten ist. Dabei sind alle Maschinen zu berücksichtigen, egal ob sie überall halten oder nur manchmal oder nirgendwo.

Hm, deine Antwort hat mich gerade in sowas wie eine kleine Krise gestürzt muss ich sagen, resp. ich würde das gerne klären. Wie siehst du folgendes:

Ich habe das Buch "Theoretische Informatik" von Hromkovic hervorgekramt und nach dem hast du recht. Ist $\mathcal{L}_{\langle \cdot \rangle}$ die Sprache aller Kodierungen von TMs, dann ist dort Nicht-Tirivialität einer Sprache $L \in \mathcal{L}_{\langle \cdot \rangle}$ darüber definiert, dass eine TM $M$ mit $\langle M \rangle \in L$ und eine TM $N$ mit $ \langle N \rangle \notin L$ gibt. Die semantische Eigenschaft von $L$ wird über
$L(A) = L(B) \Rightarrow \langle A \rangle \in L \Leftrightarrow \langle B \rangle \in L$
für TMs $A$ und $B$ definiert.
Dann gibt es (wie üblich eigentlich smile ) genau 2 triviale Sprachen: $\emptyset$ und $\mathcal{L}_{\langle \cdot \rangle}$.

Die scheinbar verbreitetere Definition die man bei Wikipedia findet (WP:Satz von Rice) nimmt aber die beiden Eigenschaften Nicht-Trivialität und Semantik zusammen, nimmt die Menge $\mathcal{P}$ aller partiellen Turing-berechenbaren Funktionen und spricht dann über eine echte Teilmenge $\mathcal{S} \subsetneq \mathcal{P}$ davon. Da wird die Nicht-Trivialität auf eine andere Menge bezogen und eine TM die nie hält würde gar nicht in betracht gezogen (da die Semantik-Eigenschaft schon "reingemixt" wurde).

Zum Beispiel wird hier:
What's a trivial property?
How do you classify properties as Trivial and Non-trivial? [duplicate]
Die Antwort gegeben:
$\{ \langle M \rangle | L(M) \in RE \}$ sei trivial. Das stimmt dann aber ja nur im Sinne der Wikipedia-Definition, denn nach deiner und Hromkovics-Definition ist diese Sprache ja eine echte Teilmenge von $\mathcal{L}_{\langle \cdot \rangle}$, denn offensichtlich ist sie nicht leer, aber es gibt natürlich auch Kodierungen von TMs, die keine Sprache akzeptieren.

Oder was meinst du dazu?

Grüsse



  Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 1943
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-19


Hallo egf,

ich sehe keinen wesentlichen Unterschied zwischen der Definition auf Wikipedia und der von mir verwendeten. Außer dass bei Wikipedia von der Menge der Funktionen selbst gesprochen wird, während ich von deren Kodierungen gesprochen habe.

Die Wikipedia-Definition zieht "alle partiellen Turing-berechenbaren Funktionen" in Betracht. Darunter ist auch die nirgendwo definierte Funktion; und diese wird gerade von einer bei keiner Eingabe haltenden Turingmaschine partiell berechnet.

Und zu dem Beispiel, das du bringst, schreibst Du

es gibt natürlich auch Kodierungen von TMs, die keine Sprache akzeptieren

Ich weiß nicht, wie Du das meinst, aber in dem zu betrachtenden Kontext (Turingmaschinen mit akzpetierenden und nicht akzeptierenden Endzuständen) stimmt diese Aussage nicht. Jede Turingmaschine akzeptiert ihren eigenen Definitionsbereich, also die Menge der Eingaben, bei denen die Maschine in einem akzeptierenden Zustand hält. Auch hier gilt wieder, dass diese Menge leer sein kann (zum Beispiel, falls die Maschine nirgendwo hält).

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



  Profil  Quote  Link auf diesen Beitrag Link
egf
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2008
Mitteilungen: 551
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-07-19


Hallo Bilbo
Cool, dass du darauf eingegangen bist, Danke smile !

2019-07-19 18:10 - Bilbo in Beitrag No. 1 schreibt:
Darunter ist auch die nirgendwo definierte Funktion; und diese wird gerade von einer bei keiner Eingabe haltenden Turingmaschine partiell berechnet.

Du meinst also ("die nirgendwo definierte Funktion") die Sprache $L=\emptyset$? Die ist ja aber sogar rekursiv, nimm einfach eine TM die sofort in den "reject"-Zustand geht.
Denn...

2019-07-19 18:10 - Bilbo in Beitrag No. 1 schreibt:
Jede Turingmaschine akzeptiert ihren eigenen Definitionsbereich, also die Menge der Eingaben, bei denen die Maschine in einem akzeptierenden Zustand hält.

... so habe ich das auch im Kopf. Das stimmt zwar für $\emptyset$, aber ...

2019-07-19 18:10 - Bilbo in Beitrag No. 1 schreibt:
Auch hier gilt wieder, dass diese Menge leer sein kann (zum Beispiel, falls die Maschine nirgendwo hält).

... wie gesagt gibt es ja aber eine TM die für $\emptyset$ immer hält (sie hält nur nie im "accept"-Zustand).

Aber eine Sprache für die es keine TM gibt, die irdenwo und irgendwann mal in "accept" oder in "reject" landet (nie hält), kann ja per Definition keine rekursiv aufzählbare Sprache sein (und von einer solchen kann man dann auch nicht von "akzeptieren" sprechen oder?).
Dennoch kann ich eine solche TM bauen und entsprechend kodieren, wie kann dann:
$\{ \langle M \rangle | L(M) \in RE \}$
trivial bzgl. Hronkovic-Definition sein?



  Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 1943
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-07-20


Hallo egf,

für jede Turingmaschine <math>M</math> ist <math>L(M) = \{w: M(w)</math> hält in einem akzeptierenden Zustand <math>\}</math> rekursiv aufzählbar. Also ist die Menge <math>\{\langle M \rangle: L(M) \in RE\}</math> die Menge aller Turingmaschinencodes.

Und nochmal: Auch eine Maschine, die niemals anhält - weder in akzeptierenden noch in verwerfenden Zuständen - akzeptiert trotzdem eine Sprache, nämlich die leere Sprache. (Klar, man kann die leere Sprache auch durch eine totale Maschine akzeptieren lassen, aber darum geht es Dir ja nicht.)

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



  Profil  Quote  Link auf diesen Beitrag Link
egf
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2008
Mitteilungen: 551
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-07-20


2019-07-20 02:45 - Bilbo in Beitrag No. 3 schreibt:
für jede Turingmaschine <math>M</math> ist <math>L(M) = \{w: M(w)</math> hält in einem akzeptierenden Zustand <math>\}</math> rekursiv aufzählbar. Also ist die Menge <math>\{\langle M \rangle: L(M) \in RE\}</math> die Menge aller Turingmaschinencodes.

Ahh, wie ärgerlich - schön auf den Punkt gebracht!



  Profil  Quote  Link auf diesen Beitrag Link
egf hat die Antworten auf ihre/seine Frage gesehen.
egf hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]