Halteproblem

[Beowulf]

Ich habe mal dieses neue Thema gestartet, um endlich von dem Beschneidungsthema wegzukommen.

Also, es geht ums Halteproblem, also ob ein Computerprogramm bestimmen kann, ob ein anderes beliebiges Programm für eine beliebige Eingabe immer anhält. (Es geht zwar genauer gesagt um Turingmaschinen, aber dies ist erstmal nicht so wichtig.)

Wenn man das Halteprogramm durch eine (mitunter natürlich recht große) Zahl darstellt, welches eine Eingabe (also das andere, zu untersuchende Programm) auf {0 , 1} ({hält nicht, hält}) abbildet, entspricht die Menge aller möglichen Abbildungen der Potenzmenge der Zahlen. Dadurch werden einfach alle möglichen Kombinationen von Nullen und Einsen dargstellt.
So gibt es bei zwei Programmen vier mögliche Ergebnisse:
leere Menge, {1}, {2}, {1, 2}
Bei drei gibt es acht Ergebnisse:
leere Menge, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}
Bei n Programmen ist die Anzahl der möglichen Abbildungen also 2^n. Sie steigt also rapide an. Kann man daher überhaupt für alle möglichen Programme alle möglichen Abbildungen bestimmen? Wenn nein, dann stellt sich die Frage, ob das Halteproblem unter den möglichen Abbildungen ist oder nicht.

So, soweit die Zusammenfassung. Das Problem trat jetzt aber schon beim Beweis für die Eigenschaft |X| < |P(X)| auf. Für endliche Mengen ist dies ja klar, da ja stets n < 2^n. Bei Unendlichkeiten ist dies wieder eine andere Sache.
Auf Wikipedia steht ja ein solcher Beweis: http://de.wikipedia.org/wiki/Halteproblem
Dieser ist aber nichts anderes als eine Abwandlung vom folgenden Satz: http://de.wikipedia.org/wiki/Satz_von_Cantor

Meine Frage an die anderen war, warum M := {x Element von A | x kein Element von f(x)} so eine zwingende Eigenschaft von Potenzmengen ist. Warum darf x kein Element von f(x) sein bzw. warum muss es eine derartige Menge M unbedingt geben, damit f surjektiv ist? Und kommt mir bitte nicht mit der leeren Menge, denn diese kann man schließlich noch gesondert behandeln.

Im folgender Abhandlung ist eigentlich ein ganz schöne, anschauliche Konstruktion eines Diagonalelementes (ab Seite 5): http://info.tuwien.ac.at/goldstern/papers/didaktik.pdf
Nur der Bezug zum allgemeinen Beweis bleibt mir noch nicht ganz klar. Und da gibts ja noch das Problem, ob das Halteproblem zu den nichtabbildbaren Elementen gehört oder nicht. Und: Würde man die Größe der zu testenden Programme begrenzen (z.B. 1MB), die des testenden Programms aber nicht, wäre das Problem dann wieder lösbar?

[elevar]

Meine Frage an die anderen war, warum M := {x Element von A | x kein Element von f(x)} so eine zwingende Eigenschaft von Potenzmengen ist. Warum darf x kein Element von f(x) sein bzw. warum muss es eine derartige Menge M unbedingt geben, damit f surjektiv ist?

M ist keine Eigenschaft, sondern ein Element von der Potenzmenge. Dass x kein Element von f(x) sein darf ist die definierende Eigenschaft von M. Diese Menge M lässt sich problemlos so bilden und sie ist offenbar eine Teilmenge von A, also ein Element von P(A). Mehr muss man nicht wissen, um im Beweis fortzufahren.

[Beowulf]

Ich verstehe dich ja schon elevar, aber ich bin halt skeptisch über das so "salopp" eingebaute x kein Element von f(x). Mir ist durchaus klar, das es Teilmengen von P(A) gibt, die x nicht enthalten. Sehr viele sogar. Aber durch x kein Element von f(x) wird bei der Definition dieser Teilmenge M vorausgesetzt, dass eine surjektive Abbildung auch ohne diese Eigenschaft funktionieren kann/muss.

Nehmen wir mal die Potenzmenge von drei Elementen, also A = {1, 2, 3}:
leere Menge, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}

Dann bilden wir mal ab:
0 => leere Menge
1 => {1}
2 => {2}
3 => {3}
4 => {1, 2}
5 => {2, 3}
6 => {1, 3}
7 => {1, 2, 3}
Es gilt: M := {x Element von A | x kein Element von f(x)}
Das gilt für folgende x von A: 0, 4, 5, 6, 7

Interessant ist, dass hier M nicht mehr im Definitionsbereich von P(A) liegt, und dass die Zahlen 4 bis 7 der Menge hinzugefügt werden mussten. Auch finde ich es wichtig, dass alle Zahlen von der Menge A gebraucht werden, um die Mengen {1}, {2}, {3} abzubilden. Da wird eigentlich schon ersichtlich, dass da auch bei unendlichen Mengen kein Spielraum für weitere Abbildungen bleibt. Die 0 ist ein extra hinzugefügtes Element, um die Nullmenge abzubilden und Probleme mit ihr bei der Beweisführung zu vermeiden. Wichtig finde ich aber auch, dass bei dieser Art der Abbildung für alle x Element von A das x Element von f(x) ist.

Die Mengen, die nur durch Elemente von A abgebildet werden, betragen n:= |A|. Die Elemente, die hinzugefügt werden mussten, betragen 2^n - n; Wenn man jetzt den Grenzwert gegen Unendlich bildet, und 2^n -n stets größer ist als n, dann weiß man, dass es stets mehr Elemente gibt die nicht abgezählt werden können als jene, die abgezählt werden können.
n < 2^n - n <=> 2n < 2^n
Bild man den Grenzwert des Quotienten, kann man nach L'Hospital auch den Grenzwert der Ableitungen bilden:
lim (2^n / 2n) = lim (n2^(n-1) / 2) = unendlich.

[DasJan]

Die Eigenschaft ist nicht "salopp eingebaut", sondern sie wird so gewaehlt. Wenn du im Supermarkt bist und da sind 100 Aepfel, dann hast du ja auch die Freiheit zu sagen: ich nehme jetzt die roten. Dazu musst du gar nicht "salopp" sein. So waehlt man sich eben hier genau die Aepfel aus, die nicht in dem Regal liegen, auf dem f(x) steht.

Was bedeutet "eine surjektive Abbildung kann ohne eine Eigenschaft funktionieren"?

f ist eine Abbildung von A nach P(A), woher nimmst du da ploetzlich 0 und 4 bis 7?

Was ist der "Definitionsbereich von P(A)"? Mengen haben keinen Definitionsbereich.

Die Schreibweise "2^n" kann man fuer unendliche Zahlen zwar sinnvoll definieren, aber so wie du den Ausdruck benutzt, funktioniert er erstmal nur fuer endliche Zahlen.

Wenn es um Maechtigkeiten von unendlichen Mengen geht, hilft L'Hospital nicht weiter, es gibt ja nicht nur ein "unendlich".

Das Jan

[Beowulf]

Wenn es um Maechtigkeiten von unendlichen Mengen geht, hilft L'Hospital nicht weiter, es gibt ja nicht nur ein "unendlich".

Klingt wie ein Paradoxon. Wenn der Quotient (nichtabbildbaren Mengen / abbildbare Mengen) gegen unendlich geht, hat man nicht nur gezeigt, dass es ein oder zwei nichtabbildbare Mengen gibt, sondern unendlich viele.

Die Eigenschaft ist nicht "salopp eingebaut", sondern sie wird so gewaehlt. Wenn du im Supermarkt bist und da sind 100 Aepfel, dann hast du ja auch die Freiheit zu sagen: ich nehme jetzt die roten. Dazu musst du gar nicht "salopp" sein. So waehlt man sich eben hier genau die Aepfel aus, die nicht in dem Regal liegen, auf dem f(x) steht.

Nein, so einfach ist das nicht. Äpfel sind nicht markiert, daher stimmt dieser Vergleich nicht. f(x) ist die Abbildung eines Elements in eine Teilmenge. Denn dass es überhaupt nennenswerte f(x) gibt bzw. geben muss, bei denen x kein Element davon ist, ist eine Annahme, kein Fakt.

[DasJan]

Was sind "abbildbare" und "nicht abbildbare" Mengen?

Wenn dich stört, dass die Äpfel nicht markiert sind, dann schreibe ich auf jeden eine Zahl. Ich mache sogar noch mehr: Ich klebe auf jeden Apfel einen Zettel, auf dem so was steht wie "jeder rote Apfel", "jeder Apfel im linken Regal" oder "die Äpfel, deren Zahl auf 2 endet". Die Zettel beschreiben dann quasi eine Abbildung von der Menge der Äpfel in die Potenzmenge der Äpfel (jeder Zettel beschreibt ja eine Teilmenge der Äpfel).

Der Satz sagt dann: es gibt eine Teilmenge der Äpfel, die auf keinem der Zettel beschrieben ist.

Das Jan

[Cohen]

Bei Äpfeln und dem Halteproblem denkt man doch zurzeit eher an das iPhone 4

[Beowulf]

Was sind "abbildbare" und "nicht abbildbare" Mengen?

Sie sind Teil meiner induktiven Beweisführung. Um mal auf mein Beispiel zurückzukommen: Nehmen wir mal an, wir könnten mit einer Turingmaschine nur die Programme {1, 2, 3} verarbeiten. Um aber alle möglichen Funktionen bilden zu können, bräuchten wir mindestens 8 (=2^3) Programme! Nun gut, wir bauen also eine Turingmaschine, die die Programme {1 ... 8} verarbeiten kann. Damit haben wir aber auch die Anzahl der möglichen Eingaben erhöht! Wir bräuchten jetzt auf einmal eine Turingmaschine, die 256 Funktionen abbilden kann. Dies kann man endlos weitertreiben.

Der Satz sagt dann: es gibt eine Teilmenge der Äpfel, die auf keinem der Zettel beschrieben ist.

Nein, so trivial sehe ich das ganze nicht. Er setzt erstmal voraus, dass es bei einer surjektiven Abbildung immer möglich ist, dass z.B. 1 kein Element von f(1) ist. Oder 456 kein Element von f(456). Und dass man aus den Elementen, bei denen dies der Fall ist, ein Element der Potenzmenge formen kann, das man wegen der Surjektivität auch abbilden können muss. Aber gerade bei meiner induktiven Beweisführung habe ich gezeigt, dass man die Funktionen derart sortieren kann, dass x immer Element von f(x) ist... abgesehen von, na, nennen wir sie mal "Singularitäten", wie die leere Menge.
Ich meine, was erwartet man auch großartig?:

Y := {x element von X | x kein Element von f(x)}
f surjektiv => es gibt ein x0 mit f(x0) = Y
x0 element von Y , x0 kein Element von f(x0) => x0 kein Element von Y => Widerspruch!
x0 element von X ohne Y , x0 Element von f(x0) => x0 Element von Y => Widerspruch!

Man definiert eine Menge mit einer Eigenschaft, die genau dem entgegenläuft was Surjektivität bedeutet. Tolle Wurst. Da hat die Abbildung aber nicht gerade eine große Chance bekommen.

[DasJan]

Nein, so trivial sehe ich das ganze nicht.

Dann siehst du das falsch. Aber noch einfacher als mit Aepfeln und Regalen kann ich es nicht erklaeren.

Y := {x element von X | x kein Element von f(x)}
f surjektiv => es gibt ein x0 mit f(x0) = Y
x0 element von Y , x0 kein Element von f(x0) => x0 kein Element von Y => Widerspruch!
x0 element von X ohne Y , x0 Element von f(x0) => x0 Element von Y => Widerspruch!

Das sieht doch schon gut aus. Fehlt nur noch die Zeile: "Folglich existiert keine surjektive Abbildung von X nach P(X)."

Uebrigens sagt man dann "q.e.d." und nicht "tolle Wurst".

Das Jan

[elevar]

Sie sind Teil meiner induktiven Beweisführung.

Dieser "Beweis" taugt leider nichts. Sei M(n) die Anzahl "nicht abbildbarer Mengen" für die Menge {1,...,n}. Du behauptest nun so etwas von der Art M(∞) = lim M(n), wobei nicht klar ist, was genau mit "∞" gemeint ist und genauso wenig klar ist, weshalb das gelten sollte.

Er setzt erstmal voraus, dass es bei einer surjektiven Abbildung immer möglich ist, dass z.B. 1 kein Element von f(1) ist. Oder 456 kein Element von f(456). Und dass man aus den Elementen, bei denen dies der Fall ist, ein Element der Potenzmenge formen kann, [...]

Wie bereits gesagt, schlimmstenfalls ist diese für dich problematische Menge eben leer. Dass man aus Elementen einer Menge X ein Element der Potenzmenge P(X) formen kann, ist keine einschränkende Forderung, sondern die Definition der Potenzmenge.

Wenn es wirklich dein Ziel ist, den Beweis zu verstehen, solltest du dir den Rat von Jan zu Herzen nehmen, und ein gutes Buch lesen. Es würde auch helfen, vorab anzuerkennen, dass der Beweis, so wie er auf der Wikipedia steht, korrekt und prinzipiell nachvollziehbar ist, und alle Schwierigkeiten damit bei dir und nicht im Beweis zu suchen sind. Wenn dabei konkrete Fragen entstehen, nur zu.

[Beowulf]

Uebrigens sagt man dann "q.e.d." und nicht "tolle Wurst".

Nein, ich möchte von dir einen Beweis sehen, der folgendes zeigt: Für jede surjektive Abbildung f: X -> P(X) gibt es auf jedem Fall eine Menge A Element von P(X) für die gilt: A: {x Element von X | x kein Element von f(x)}
Du wirst schnell merken, dass dies der eigentliche Beweis ist und nicht so trivial ist, wie man vielleicht glauben möchte. Klar, man kann mit der leeren Menge argumentieren, aber das Ergebnis ist nicht befriedigend, da man für diese eine spezielle Menge eine Sonderregelung treffen kann. Um zu zeigen, dass es unendlich viele Mengen gibt die man nicht abbilden kann, muss man zeigen, dass diese spezielle Menge bei allen möglichen surjektiven Abbildungen nicht immer die gleiche (z.B. die leere Menge) ist... und dass diese immer unendlich groß ist. Das wäre ja alles sonst ziemlich witzlos.

Dieser "Beweis" taugt leider nichts. Sei M(n) die Anzahl "nicht abbildbarer Mengen" für die Menge {1,...,n}. Du behauptest nun so etwas von der Art M(∞) = lim M(n), wobei nicht klar ist, was genau mit "∞" gemeint ist und genauso wenig klar ist, weshalb das gelten sollte.

Nein, ich habe keinen Grenzwert über eine Menge gebildet, sondern über deren Elementanzahl. Das ist ein Unterschied.

[elevar]

Dieser "Beweis" taugt leider nichts. Sei M(n) die Anzahl "nicht abbildbarer Mengen" für die Menge {1,...,n}. Du behauptest nun so etwas von der Art M(∞) = lim M(n), wobei nicht klar ist, was genau mit "∞" gemeint ist und genauso wenig klar ist, weshalb das gelten sollte.

Eigentlich war das nur gut gemeint. Ich wollte dir helfen zu verstehen, wo der Denkfehler ist.

Dass dich selbst Autoritäten wie Cantor oder gar Jan nicht zum zweifeln oder auch nur grübeln bringen, zeugt von beeindruckendem Selbstvertrauen

[DasJan]

Uebrigens sagt man dann "q.e.d." und nicht "tolle Wurst".

Nein, ich möchte von dir einen Beweis sehen, der folgendes zeigt: Für jede surjektive Abbildung f: X -> P(X) gibt es auf jedem Fall eine Menge A Element von P(X) für die gilt: A: {x Element von X | x kein Element von f(x)}

Streng genommen muss das nicht bewiesen werden, das ist naemlich genau die Aussage vom Aussonderungsaxiom. Aber ich will versuchen, es dir plausibel zu machen: A = {x Element von X | x kein Element von f(x)} ist eine Teilmenge von X. Vielleicht die leere, vielleicht nicht die leere. Aber es ist auf jeden Fall eine Teilmenge von X. Und weil P(X) alle Teilmengen von X enthaelt, enthaelt P(X) insbesondere auch A.

Es gibt zwei Moeglichkeiten:
1. Millionen von Mathestudenten, die das in ihrem Studium mal gesehen haben, und alle Mathematik-Professoren auf der Welt haben den Beweis faelschlicherweise fuer korrekt gehalten.
2. Der Beweis ist korrekt.

Gibst du wenigstens zu, das Moeglichkeit 2 die wahrscheinlichere ist?

Dass dich selbst Autoritäten wie Cantor oder gar Jan nicht zum zweifeln oder auch nur grübeln bringen, zeugt von beeindruckendem Selbstvertrauen

Also bitte. Im Zweifel rate ich immer dazu, eher auf Cantor zu hoeren als auf mich.

Das Jan

[elevar]

Also bitte. Im Zweifel rate ich immer dazu, eher auf Cantor zu hoeren als auf mich.

Bis auf in Sachen Adventure-Tests. Da ist im Übrigen auch einfach wenig überliefert...

[DasJan]

Wenn ich mir die Menge aller Dinge anschaue, die Cantor ueber Adventures gesagt hat, dann muss ich gestehen, dass ich jeder einzelnen voll zustimmen muss!

Das Jan