Jenseits von Chomsky
-
Ein Beispiel ist das Halteproblem.
Hier geht es um Grammatiken ... haeh? Was hat das mit entscheidbar zu tun? Auch kann ich einen Automaten/Turingmaschine konstruieren, die eine berechenbare Funktion fuer das Halteproblem realisiert. Tja, nicht entscheidbar, aber doch berechenbar.
-
knivil schrieb:
Ein Beispiel ist das Halteproblem.
Hier geht es um Grammatiken ... haeh?
Ich dachte um sprachen?
-
Der echte Informatikker schrieb:
Ich dachte um sprachen?
Dann waehle eine Sprache und loese das Halteproblem ... (Grammatiken erzeugen Sprachen). Normal habe ich nicht die Menge "Halteproblem" mit einer Sprache identifiziert. Wobei eine Sprache auch nur eine Menge von Woertern ist und ich sehe gerade nicht, wie das Halteproblem eine Menge von Woertern sein kann.
Ich haette jetzt eine Idee, aber ich glaube kaum, dass du mit deinen eher Wortkargen Antworten das gemeint hast. Wobei es auf Russel's Paradox hinauslaeuft und man sich streitet, ob das ueberhaupt eine Menge ist.
Die Menge aller Woerter, die eine Turingmaschine beschreiben, welche auf der Eingabe ihrer eigenen Beschreibung nicht halten.
-
was nicht rekursiv aufzählbar ist, ist nicht Typ-0, oder ? Also suchen wir eine Teilmenge von {0,1}*, die nicht r.a. ist.
Mir fällt gerade keine ein
-
Ein Programm kannst du mit einer Gödelzahl identifizieren. Das Halteproblem kannst du demnach mit der Menge der Gödelzahlen der Programme identifizieren, die halten wenn man ihnen das eigene Program als Gödelzahl als Eingabe übergibt. Diese Menge kannst du kodieren (z.b. Zehnersystem) und erhält eine Menge von Wörtern (auch Sprache genannt). Du kannst also sagen, das Entscheidungsproblem dieser Sprache ist äquivalent zum Halteproblem. So viel zur Klärung der Begrifflichkeiten.
Dies ist jedoch kein Beispiel für eine Sprache die nicht in CH-0 liegt (also eine Sprache für die es keine erzeugende Grammatik gibt). Wenn das Wortproblem einer Sprache semi-entscheidbar ist, genau dann gibt gibt es eine CH-0 Grammatik. Das Halteproblem ist semi-entscheidbar, denn man kann die Turingmaschine einfach laufen lassen. Demnach gibt es eine CH-0 Sprache welche diese Halteproblem-Sprache erzeugt.
Die selbe Konstruktion mit einem Problem, welches nicht semi-entscheidbar ist müsste aber eine Sprache liefern, welche nicht in CH-0 liegt. Also zum Beispiel das Komplement des Halteproblem.
-
Genau das habe ich beschrieben, aber ist das eine Menge im Sinne von ZFC?
-
knivil schrieb:
Genau das habe ich beschrieben, aber ist das eine Menge im Sinne von ZFC?
Also eine echte Klasse ist es schonmal nicht, schließlich ist es in der Menge aller Turingmaschinen enthalten -- oder wenn man es eben über die Kodierung in den natürlichen Zahlen, dann ist es eine Teilmenge der natürlichen Zahlen. Das sollte dann wohl schon eine Menge sein.
-
Naja, aber das war doch auch Goedel's Problem. Ist doch alles irgendwie das gleiche wie Russell.
wikipedia schrieb:
ZFC does not assume that, for every property, there is a set of all things satisfying that property.
Dort ist der Typ, auf den property angewandt wird, nicht naeher spezifiziert. Und Goedel hat es halt nur mit den natuerlichen Zahlen gemacht.
-
Wenn ich eine Menge habe (zum Beispiel die natürlichen Zahlen), dann ist doch jede Teilmenge eine Menge: Die Teilmenge ist Element der Potenzmenge (und die ist (nach ZFC-Axiom) eine Menge. Also kann die Teilmenge keine echte Klasse sein.
Ich sehe auch nicht ein, wo das dasselbe sein soll wie bei Goedel (was genau von Gödel eigentlich?). Mir scheint das eine ist ein Diagonalisierungsargument, während das andere am naiven Mengenbegriff scheitert. Wo ist die Gemeinsamkeit?
-
@knivil & Jester:
Redet ihr jetzt über das Fundierungsaxiom? Oder falsches Märchen?!
http://de.wikipedia.org/wiki/Fundierungsaxiom
-
Jetzt erstaunt ihr mich doch ein wenig. Dachte es ist Allgemeinwissen, dass man alle Probleme auch als Wortprobleme definieren kann, d.h. als das Problem zu entscheiden ob ein Wort x in einer Sprache L liegt.
Auf dieser Basis kann man das Halteproblem als ein Wortproblem formulieren und die zugehörige Sprache ist keine CH0-Sprache, da es keine Turing-Maschine gibt die entscheiden kann ob ein Wort in dieser Sprache liegt (oder eben nicht darin liegt).
-
Der echte Informatikker schrieb:
Jetzt erstaunt ihr mich doch ein wenig. Dachte es ist Allgemeinwissen, dass man alle Probleme auch als Wortprobleme definieren kann, d.h. als das Problem zu entscheiden ob ein Wort x in einer Sprache L liegt.
Auf dieser Basis kann man das Halteproblem als ein Wortproblem formulieren und die zugehörige Sprache ist keine CH0-Sprache, da es keine Turing-Maschine gibt die entscheiden kann ob ein Wort in dieser Sprache liegt (oder eben nicht darin liegt).Ok, hier ein Beweis: http://www.inf.uni-konstanz.de/algo/lehre/ss02/theo/skript.pdf Seite 84 Satz 5.4
Die von Typ–0–Grammatiken G erzeugten Sprachen sind rekursiv aufzählbar.
Und noch eine Folie: http://www.grundstudium.info/theorie/node42.php
-
Der echte Informatikker schrieb:
da es keine Turing-Maschine gibt die entscheiden kann ob ein Wort in dieser Sprache liegt (oder eben nicht darin liegt).
Das Halteproblem ist aber semi-entscheidbar und CH-0 Sprachen sind gerade die semi-entscheidbaren.
-
Der echte Informatikker schrieb:
Jetzt erstaunt ihr mich doch ein wenig. Dachte es ist Allgemeinwissen, dass man alle Probleme auch als Wortprobleme definieren kann, d.h. als das Problem zu entscheiden ob ein Wort x in einer Sprache L liegt.
IMHO geht es genau um dieses "alle Probleme"! Probleme sind ein menschliches Konzept ebenso, wie die symbolische Formulierung für das Eingabeband. Darauf zielt doch die Eingangsfrage ab.
Der echte Informatikker schrieb:
Auf dieser Basis kann man das Halteproblem als ein Wortproblem formulieren und die zugehörige Sprache ist keine CH0-Sprache, da es keine Turing-Maschine gibt die entscheiden kann ob ein Wort in dieser Sprache liegt (oder eben nicht darin liegt).
Warum die Berechbarkeitsbeschreibung nicht zwingend in CH-0 liegen kann ich nicht nachvollziehen, denn es muss sich nicht um die selbe Turing handeln. Ein Ansatz wo dies z.Z. heiß gefahren wird, sind die sogenannten Coherent Languages
http://en.wikipedia.org/wiki/Wide-spectrum_language
http://www.springerlink.com/content/c452556l1p67tu37/
http://qwiki.stanford.edu/wiki/Complexity_Zoo:C => Komplexitätsklasse 'Coh'Zelluarare Automaten ist ein Thema außerhalb von CH-x und IMO abstrakte Räume die eine Mischung aus CA und CH darstellen.
-
Unsicherer schrieb:
Der echte Informatikker schrieb:
da es keine Turing-Maschine gibt die entscheiden kann ob ein Wort in dieser Sprache liegt (oder eben nicht darin liegt).
Das Halteproblem ist aber semi-entscheidbar und CH-0 Sprachen sind gerade die semi-entscheidbaren.
Dann eben doch, wie schon oben vorgeschlagen, das Komplement. Imo ist damit die Frage geklärt, oder?
-
Jester schrieb:
Unsicherer schrieb:
Der echte Informatikker schrieb:
da es keine Turing-Maschine gibt die entscheiden kann ob ein Wort in dieser Sprache liegt (oder eben nicht darin liegt).
Das Halteproblem ist aber semi-entscheidbar und CH-0 Sprachen sind gerade die semi-entscheidbaren.
Dann eben doch, wie schon oben vorgeschlagen, das Komplement. Imo ist damit die Frage geklärt, oder?
Klar, hab es ja selbst vorgeschlagen. Allerdings ändert das nichts daran, dass die zitierte Behauptung falsch ist.
-
@Der echte Informatikker: Sorry, deine ersten Antworten waren einfach zu kurz und unkonkret.
Unsicher schrieb:
Klar, hab es ja selbst vorgeschlagen.
Klar, habe wir alle.
PS: Auch habe ich mir Logikbuch gekauft, um herauszufinden, ob die Halteproblemmenge eine Menge im Sinne ZFC ist. Kann ja meine Erkenntnisse posten ... so in einem halben Jahr.
-
knivil schrieb:
PS: Auch habe ich mir Logikbuch gekauft, um herauszufinden, ob die Halteproblemmenge eine Menge im Sinne ZFC ist. Kann ja meine Erkenntnisse posten ... so in einem halben Jahr.
Stichwort Aussonderungsaxiom.