Beispiel einer aufzählbaren aber nicht entscheidbaren Menge |
| 18.12.2007, 01:16 | Urza | Auf diesen Beitrag antworten » | ||||
| Beispiel einer aufzählbaren aber nicht entscheidbaren Menge Ich habe eine Frage aus dem Gebiet der Logik bzw. genauer der Berechenbarkeitstheorie. Ich weiß über Berechenbarkeitstheorie fast nichts bis jetzt. Sei A ein endliches Alphabet (Menge von Zeichen) und A* die Menge der Zeichenketten aus Zeichen in A. Ich suche für irgendein konkretes A (z.B. A={'1'}, A*=IN sozusagen) eine Teilmenge M von A, sodass M aufzählbar, aber nicht entscheidbar ist. D.h. es soll einen Algorithmus geben, der nacheinander alle Elemente von M aufzählt, aber es soll keinen Algorithmus geben, der als Eingabe ein beliebiges Element von A* nimmt und als Ausgabe "ja" oder "nein" liefert, je nach dem, ob die Eingabezeichenkette in M liegt oder nicht (und der immer nach endlicher Zeit fertig wird). Ich bin mir im Moment garnicht sicher, ob es sowas überhaupt geben kann. Falls es sowas nicht geben kann, suche ich einen passenden Beweis 
Gruß, Urza |
||||||
| 18.12.2007, 03:37 | lego | Auf diesen Beitrag antworten » | ||||
ist das nicht ein thema der theoretischen informatik? |
||||||
| 18.12.2007, 05:31 | Urza | Auf diesen Beitrag antworten » | ||||
Das wohl auch. Aber es ist eigentlich finde ich eine sehr mathematische Frage. Zur Motivation: Wenn wir über ein bestimmtes mathematisches Objekt reden, reden wir im Prinzip immer über eine Zeichenkette, ein Symbol, weil wir in der Mathematik alles durch Symbole darstellen können. Terme, Aussagen und Beweise können alle offensichtlich eindeutig durch Zeichenketten beschrieben werden. Genauso auch Mengen, sofern wir ihre Definition wirklich hinschreiben können und die Existenz nicht nur abstrakt aus den Axiomen der Mengenlehre folgt (solche "Mengen" mal außen vor gelassen). Außerdem sieht man, dass man nur endlich viele Ausgangszeichen braucht und auch nicht mehr zu Verfügung hat - kein Mathematiker hat jemals in seinem Leben unendlich viele Zeichen benutzt (wobei aber abzählbar viele im Sinne von beliebig viele schon vorhanden und nötig sind, da aus endlich vielen erzeugbar, z.B. natürliche Zahlen aus den Zeichen "0","1",..,"9"). Überabzählbare Megen und auch nicht mit einem Algorithmus beschreibbare abzählbare Mengen sind folglich ein rein abstraktes Konstrukt, das man erstmal ohne Beschränkung der Allgemeinheit außer Acht lassen kann. Nun also die Frage in vielleicht etwas anderem Licht: Wenn wir eine beliebige Menge (von Zeichenketten aus endlichen Zeichen, was wie gesagt keine echte Einschränkung für eine konkret gegebene Menge ist) gegeben haben, zu der eine Vorschrift existiert, die sie definiert, d.h. ein Algorithmus, der nacheinander alle ihre Elemente ausgibt. Ist dann die Aussage "x ist ein Element von M" für beliebige solche Zeichenketten x entscheidbar? D.h. können wir anhand der gegebenen Bildungsvorschrift für M schon immer beweisen, dass ein gegebenes Objekt sich daraus erzeugen lässt oder das Gegenteil beweisen? D.h. gibt es einen Algorithmus, der als Eingabe so eine Zeichenkette x zusammen mit einem Algorithmus hat, der eine Menge M erzeugt, und der ausgibt, ob x sich mit dem Eingabealgorithmus erzeugen lässt? Das könnte denke ich Aufschlüsse darüber liefern, ob eine wahre Aussage (z.B. "x ist kein Element von M") immer beweisbar sein muss. |
||||||
| 18.12.2007, 10:16 | Tobias | Auf diesen Beitrag antworten » | ||||
Wenn M aufzählbar ist, dann ist M in jedem Fall semi-entscheidbar (die Begriffe werden äquivalent genutzt). Semi-entscheidbar heißt, dass es einen Algorithmus (Turingmaschine) gibt, der für "ja" ausgibt, aber für keine Ausgabe produziert. Was du nun also suchst ist eine nicht entscheidbare Menge / Sprache, die semi-entscheidbar ist. Populäres Beispiel ist das Halteproblem. Ein weiteres ist hier beschrieben: Diophantische Gleichungen. |
||||||
| 18.12.2007, 20:25 | Urza | Auf diesen Beitrag antworten » | ||||
Ich habe mir das mit dem Halteproblem bei wikipedia mal angesehen. Ich verstehe etwas an dem Widerspruchsbeweis nicht : Die Argumentation läuft so (vereinfacht) : Angenommen, es gibt einen Algorithmus 'haltetest', der als Eingabe die Kodierung eines Algorithmus (als Zeichenkette) nimmt und als Ausgabe die Zeichenkette "ja" oder "nein", je nach dem ob der Eingabealgorithmus hält oder nicht hält (und welcher auch immer selber hält), wobei als Eingabe z.B. immer das leere Wort dienen kann. Dann sei ein Algorithmus 'test' so definiert (Pseudo-Code): "solange haltetest(test) : tu nichts." Nun führt die Frage, ob test bei Eingabe des leeren Wortes hält zu einem Widerspruch. Meine Frage jetzt: Wie kann ein Algorithmus seine eigene Beschreibung übergeben, wie test es tut? Zum Beispiel muss es ja ein Zeichen wie " geben, um zwischen dem kodierten Quelltext und dem eigentlichen Quelltext unterscheiden. Dieses Zeichen muss im kodierten Quelltext aber auch vorkommen, was zu Problemen führen würde. Außerdem würde man vielleicht niemals fertig, die eigene Beschreibung hinzuschreiben, weil die Beschreibung der Beschreibung auch zur Beschreibung gehört. Man könnte einen neuen Algorithmus "hilf" definieren, der nur die Beschreibung von "test" ausgibt und der dann in "test" aufgerufen wird. Aber diesen müsste man auch irgendwie in "test" unterbringen können, damit es ein zusammenhängender Algorithmus wird (wenn in einem Algorithmus Funktionen vorkommen, deren Definition nicht erwähnt wird, dann kann man von haltetest sowieso nicht erwarten, eine Ausgabe zu liefern). Und dann würde sich auch wieder die Beschreibung des zusammengesetzten Algorithmus ändern. |
||||||
| 19.12.2007, 01:28 | Tobias | Auf diesen Beitrag antworten » | ||||
Test übergibt nicht seine eigene Beschreibung sondern bekommt seine eigene Beschreibung als Parameter. Das ist ein Unterschied. Man kann eine beliebige Turingmaschine M eindeutig als Wort <M> kodieren. Die Sprache alle Turingmaschinen ist entscheidbar (und nach Church-Turing-These haben wir so eine Aufzählung aller "Problemlöser"). Ferner kann eine andere Turingmaschine Interpretercode enthalten, der auf dem Eingabeband die kodierte Form einer Turingmaschine liest und diese TM dann emuliert. |
||||||
| Anzeige | ||||||
|
|
||||||
| 19.12.2007, 08:57 | Airblader | Auf diesen Beitrag antworten » | ||||
Mal 'ne Frage zum Anfangsposting: Warum sollte für dieses A dann sein 
Unter einer Zeichenkette verstehe ich zunächst die Aneinandersetzung von Zeichen. Hier also 1, 11, 111, 1111, 11111, ... aber nicht 1+1=2, 1+1+1=3, ... Oder soll eine "Zeichenkette" eben so definiert sein? air |
||||||
| 19.12.2007, 12:32 | Tobias | Auf diesen Beitrag antworten » | ||||
Ich glaube, was Urza sagen wollte ist, dass ein Modell der Peano-Axiome ist und man es somit auch als bezeichnen könnte. Ein anderes Modell findest du hier. Wenn du mit Addition argumentierst, muss man anmerken, dass es eine Operation gibt, die Konkatenation von Wörtern, so dass . Letztendlich geht es hier nur um die Symbolwahl für ein Element der natürlichen Zahlen. Ob man die drei als "3" oder als "111" darstellt, ist Jacke wie Hose. |
||||||
| 19.12.2007, 14:12 | Airblader | Auf diesen Beitrag antworten » | ||||
Überzeugt 
air |
||||||
| 19.12.2007, 22:05 | Urza | Auf diesen Beitrag antworten » | ||||
Oh stimmt, das habe ich falsch gelesen. Vielleicht ist das Halteproblem ja wenigstens für Algorithmen lösbar, die keine Eingabeparameter haben?
Damit muss ich mich mal genauer beschäftigen. Also es ist möglich, einen Algorithmus zu schreiben (ob in C oder als Turingmaschine sollte ja egal sein?), der als Eingabe den Quellcode eines Programmes nimmt (bzw. die kodierte Turingmaschine) und den dann als Teil des eigenen Algorithmus (wie eine Funktion) ausführt? |
||||||
| 19.12.2007, 22:51 | Tobias | Auf diesen Beitrag antworten » | ||||
Das ist genau das, was Interpreter machen: http://de.wikipedia.org/wiki/Interpreter |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
