Hinweis auf die DSGVO: Auf unserer Seite werden keine Dritt-Anbieter-Cookies verwendet und nur Daten erfasst, welche für das Minimum an Board-Funktionalität notwendig sind.
Bevor Sie sich registrieren oder das Board verwenden, lesen Sie bitte zusätzlich die DSGVO-Erklärung, welche in der Navigationsleiste verlinkt ist.

Kurzfassung der unserer Meinung nach wichtigsten DSGVO-Punkte:
Es kann vorkommen, dass Benutzer eigenverantwortlich Videos oder sonstige Medien in ihren Beiträgen verlinken, welche beim Aufruf der Forenseite als Teil der Seite samt zugehörigem Material mitgeladen werden. Sollten Sie dies nicht wünschen, verwenden Sie beim Benutzen des Forums einen Blocker wie z.B. uMatrix, welcher das Laden von Inhaltsblöcken von Fremd-URLs effektiv unterbinden kann.
Wir blenden keine Werbung ein und schränken die Inhalte in keinster Weise bei Benutzung von Addblockern ein. Dadurch ist die Grundfunktionalität des Forums auch bei vollständigem Blockieren von Drittanbieter-Inhalten stets gegeben.

Cookies werden unsererseits nur verwendet um das Einloggen des Benutzers für die Dauer der Forenbenutzung zu speichern. Es steht dem Benutzer frei die Option 'Angemeldet bleiben' zu verwenden, damit der Cookie dauerhaft gespeichert bleibt und beim nächsten Besuch kein erneutes Einloggen mehr notwendig ist.
EMail-Adressen werden für Kontakt bei wichtigen Mitteilungen und zur Widerherstellung des Passwortes verwendet. Die verwendeten IPs können von uns ohne externe Hilfsmittel mit keiner realen Person in Verbindung gebracht werden und werden nach spätestens 7 Tagen gelöscht. Diese IPs werden höchstens verwendet um Neuanmeldungen unerwünschter oder gesperrter Nutzer zu identfizieren und zu unterbinden. Wir behalten uns daher vor bei Verdacht, die Frist für die IP-Löschung auf maximal 14 Tage zu verlängern.
Unsere Webseite läuft auf einem virtuellen Linux-Server, welcher von einem externen Anbieter gehostet wird. Etwaige Verstöße der DSGVO-Auflagen seitens dieses deutschen Hosters können wir nicht feststellen und somit auch nicht verfolgen.
Wir halten Backups unserer Datenbanken, welche in regelmäßigen Abständen als Schutz vor Katastrophen, Hackerangriffen und sonstigen Ausfällen erstellt werden. Sollte ein Nutzer die Löschung seiner Daten wünschen, betrachten wir es als Unzumutbar die Backups auch von den Daten zu befreien, da es sich hierbei um eine mehrtägiges Unterfangen handelt - dies ist für eine Einzelperson beim Betrieb eines privaten Forums nicht zumutbar möglich ohne das Backup komplett zu löschen.
Sollten Sie etwas gegen die dauerhafte anonyme Speicherung ihrer EMail-Adresse, ihres Pseudonyms und ihrer Beiträge in einem Backup haben, sehen Sie von der Registrierung in diesem Forum ab. Für Mitglieder, welche vor dem 25.05.2018 registriert waren steht jedoch das Recht im Raum, eine Löschung der Datenbank-Backups zu beantragen.



Wenn dies Ihr erster Besuch hier ist, lesen Sie bitte zunächst die FAQs sowie die wesentlichen Regeln zur Benutzung des Forums.
Um an den Diskussionen teilnehmen zu können, müssen Sie sich zunächst registrieren.

nicht-berechenbare Mengen

Mathematische Fragestellungen
Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: nicht-berechenbare Mengen

Beitrag von tomS » 17. Sep 2017, 10:18

Ich denke, wir sind (und ich war) hier sprachlich unpräzise.

Eine Aussage ist beweisbar, wenn innerhalb eines Axiomensystems ein endlicher Beweis für diese Aussage existiert.
Eine Zahl ist berechenbar, wenn ein endlicher und in endlich vielen Schritten terminierender Algorithmus (eine Turingmaschine) existiert, der diese Zahl als Ergebnis ausgibt.

D.h. dass sich Beweisbarkeit auf Aussagen und Berechenbarkeit auf Zahlen (u.a. mathematische Objekte) bezieht. Damit sind beide Begriffe m.E. nicht identisch, sie sind jedoch verwandt und für bestimmte Probleme unter bestimmten Voraussetzungen äquivalent.

Es gibt jedoch auch Fälle, anhand derer man explizit erkennt, dass diese Begriffe i.A. nicht identisch sind. Z.B. kann man in ZFC die Existenz bestimmter Zahlen und Objekte beweisen, ohne sie berechnen bzw. konstruieren zu können. Man kann sogar beweisen, dass letzteres nicht funktioniert: es gibt überabzählbar viele reelle Zahlen jedoch nur abzählbar viele Turimgmaschinen mit Input; deswegen können nicht alle reellen Zahlen berechenbar sein; umgekehrt: "fast alle" reellen Zahlen sind nicht-berechenbar.

Ein explizites Beispiel für eine nicht-berechenbare Zahl ist die Chaitinsche Konstante, die beweisbar existiert jedoch ebenso beweisbar nicht berechenbar ist.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: nicht-berechenbare Mengen

Beitrag von Skeltek » 17. Sep 2017, 23:32

Wetten wir, man kann durch ein Diagonalargument beweisen, dass es zu jeder beliebigen abzählbar unendlichen Menge an Algorithmen, immer mindestens einen Algorithmus gibt, welcher die Termination aller Algorithmen in der Liste voraussagen kann?
Egal welche Algorithmen man aufzählt, es bleibt immer mindestens ein möglicher Algorithmus übrig, welcher die Termination aller aufgezählten vorhersagen kann.
So gesehen wäre beweisbar, dass ein Algorithmus existiert, allerdings kann man ihn nicht benennen oder angeben, er ist sozusagen 'transzendent'.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: nicht-berechenbare Mengen

Beitrag von tomS » 18. Sep 2017, 06:23

Du meinst einen reinen Existenzbeweis, aus dem sicher die Existenz folgt, jedoch gerade nicht, welcher der Algorithmen dies ist?

Ich denke, dass auch das gem. der Sätze von Gödel und Turing widerlegt ist:

https://de.m.wikipedia.org/wiki/Halteproblem

Hier wird explizit gezeigt, dass das Halteproblem auch für die reine Existenzfrage auf einen Widerspruch führt.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Benutzeravatar
seeker
Ehrenadmin
Ehrenadmin
Beiträge: 8098
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 18. Sep 2017, 09:29

tomS hat geschrieben:gibt es auch ein einfaches Beispiel einer nicht-berechenbaren Untermenge der natürlichen Zahlen?
Hierzu ist mir noch eingefallen, dass das auch für alle zufällig gewählten Teilmengen aus N gilt (es muss ja nicht gleichverteilt-zufällig gewählt werden).
Dass diese Zahlenmengen existieren scheint mir allerdings nicht auf einem nicht-konstruktiven Beweis zu beruhen, sondern eher auf einer Definition/Grundannahme, die da lautet: "Zahlen können zufällig gewählt werden!"
Das geht also auch, ist aber wohl nicht das, was du im Sinn hattest, jedoch in gewisser Weise das einfachste Beispiel. :)
seeker hat geschrieben:
15. Sep 2017, 14:24
Man muss hier nur unterscheiden, ob der Algorithmus nur einseitig oder auch zweiseitig funktioniert (bzw. ob ein solcher existiert), ob er also auch bei Input (geraten) = "falsch" irgendwann fertig wird und ein Ergebnis liefert.
Das hier war mir wichtig, weil der Algorithmus "alles durchprobieren" oft nur einseitig funktioniert.
Das wär dann bei der Rado-Funktion so:

10 n = 0
20 Lasse eines der Programme bb(n) laufen und stelle fest, wie viele Striche x(i) es zeichnet (und damit auch ob es hält)
30 Merke dir x(i)
30 Springe zu 20, falls noch nicht alle Programme bb(n) ausprobiert sind, sonst springe zu 40
40 Vergleiche alle gemerkten x(i) und gebe das größte x(i) aus
50 n = n+1
60 Springe zu 20

Wenn wir nur ein spezielles n von bb(n) untersuchen wollen, dann lassen wir die Zeilen 50 und 60 weg.
Für z.B. n = 4 erhalten wir:

10 n = 4
20 Lasse eines der Programme bb(n) laufen und stelle fest, wie viele Striche x(i) es zeichnet (und damit auch ob es hält)
30 Merke dir x(i)
30 Springe zu 20, falls noch nicht alle Programme bb(n) ausprobiert sind, sonst springe zu 40
40 Vergleiche alle gemerkten x(i) und gebe das größte x(i) aus

Das Problem:
Dieses Programm hält nicht, falls auch nur ein bb(4) nicht hält, es entscheidet das Problem also nur partiell und ist somit nicht sicher zur Lösung der Frage geeignet, die nach dem größten x(i) sucht.
tomS hat geschrieben:
15. Sep 2017, 15:01
Some Busy Beaver enthusiasts have opined that even BB(6) will never be known exactly. On the other hand, the abstract argument from before tells us only that, if we confine ourselves to (say) ZF set theory, then there’s some k—possibly in the tens of millions or higher—such that the values of BB(k), BB(k+1), BB(k+2), and so on can never be proven. So again: is the number of knowable values of the BB function more like 10, or more like a million?

This is the question that Adam and I (but mostly Adam) have finally addressed.

...

Of course, three orders of magnitude still remain between the largest value of n (namely, 4) for which BB(n) is known to be knowable in ZFC-based mathematics, and the smallest value of n (namely, 7,918) for which BB(n) is known to be unknowable.
Das muss auf einem ein nichtkonstruktiven Beweis beruhen.

Ich habe damit allerdings noch ein Problem:
Wir wissen, dass die Menge der Algorithmen bb(n) überabzählbar-unendlich groß ist, es aber bei n e N nur abzählbar-unendlich viele n gibt. Daher muss es hier nicht-berechenbare x(i) von bb(n) geben. Aber wo soll der Übergang sein? Bei n = 3 sind es abzählbar endlich viele Algorithmen bb(n), bei n = 4 auch, es kann doch nicht sein, dass es bei n = 7918 überabzählbar-unendlich viele sind, denn dann hätten wir irgendwo davor einen Unendlichkeitsübergang gehabt: z.B. wären es bei n = 7917 noch endlich viele gewesen und dann bei n = 7918 nicht mehr, das geht nicht.
Es geht mir hier um die prinzipielle Unberechenbarkeit, die praktische ist klar...
Grüße
seeker


Wissenschaft ... ist die Methode, kühne Hypothesen aufstellen und sie der schärfsten Kritik auszusetzen, um herauszufinden, wo wir uns geirrt haben.
Karl Popper

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: nicht-berechenbare Mengen

Beitrag von tomS » 18. Sep 2017, 11:13

seeker hat geschrieben:
18. Sep 2017, 09:29
Das muss auf einem ein nichtkonstruktiven Beweis beruhen.
Das ist wohl so.
seeker hat geschrieben:
18. Sep 2017, 09:29
Wir wissen, dass die Menge der Algorithmen bb(n) überabzählbar-unendlich groß ist
Nein, die Menge der Algorithmen ist abzählbar unendlich.

Das ist recht einfach einzusehen: jeder Algorithmus ist ein Computerprogramm aus endlich vielen Zeichen bzw. eine endliche Turingmaschine; diese kann man z.B. alphanumerisch sortieren und erhält daraus eine abzählbare Liste.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Benutzeravatar
seeker
Ehrenadmin
Ehrenadmin
Beiträge: 8098
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 18. Sep 2017, 11:48

tomS hat geschrieben:
18. Sep 2017, 11:13
Nein, die Menge der Algorithmen ist abzählbar unendlich.

Das ist recht einfach einzusehen: jeder Algorithmus ist ein Computerprogramm aus endlich vielen Zeichen bzw. eine endliche Turingmaschine; diese kann man z.B. alphanumerisch sortieren und erhält daraus eine abzählbare Liste.
Ja, ok, Lapsus. Die Menge aller Funktionen ist überabzählbar-unendlich.
Mein Verständnisproblem bleibt damit bestehen.
Grüße
seeker


Wissenschaft ... ist die Methode, kühne Hypothesen aufstellen und sie der schärfsten Kritik auszusetzen, um herauszufinden, wo wir uns geirrt haben.
Karl Popper

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: nicht-berechenbare Mengen

Beitrag von tomS » 18. Sep 2017, 12:03

seeker hat geschrieben:
18. Sep 2017, 11:48
Mein Verständnisproblem bleibt damit bestehen.
Erklär' nochmal.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: nicht-berechenbare Mengen

Beitrag von Skeltek » 18. Sep 2017, 20:46

Ja, das ist der entscheidende Punkt, die betrachteten Algorithmen werden a priori auf nur endliche Algorithmen festgelegt.
Aber das ist doch dasselbe wie mit Zahlen: Jede abzählbar unendliche Liste an Algorithmen ist unvollständig, selbst wenn man diese nicht auf Algorithmen beschränkt welche aus einer endlichen Anzahl an Instruktionen bestehen.
Ein Program ist endlich... okay. Aber ein Algorithmus?
Mir ging es mehr um die Unvollständigkeit beider Mengen. Natürlich existiert kein endlicher Algorithmus; da hast du völlig recht.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: nicht-berechenbare Mengen

Beitrag von tomS » 18. Sep 2017, 21:20

Skeltek hat geschrieben:
18. Sep 2017, 20:46
Ja, das ist der entscheidende Punkt, die betrachteten Algorithmen werden a priori auf nur endliche Algorithmen festgelegt.
Ein Algorithmus ist per Definitionen eine endliche Anweisungslisze bzw. ein endliches Programm mit endlichem Input. Oder anders gesagt, es entspricht einer Turingmaschine mit endlich vielen Zuständen und endlichem Input aus einem endlichen Alphabet.
Skeltek hat geschrieben:
18. Sep 2017, 20:46
Jede abzählbar unendliche Liste an Algorithmen ist unvollständig, selbst wenn man diese nicht auf Algorithmen beschränkt welche aus einer endlichen Anzahl an Instruktionen bestehen.
Doch, die Liste ist eben gerade nicht unvollständig; die Liste der endlichen Algorithmen ist konstruierbar, bzw. die endlichen Algorithmen sind aufzählbar.
Skeltek hat geschrieben:
18. Sep 2017, 20:46
Mir ging es mehr um die Unvollständigkeit beider Mengen.
nein - s.o.

Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar. Man startet mit einem endlichen Alphabet, z.B. {a ... z, A ... Z, 0 ... 9} plus die Menge der erlaubten Sonderzeichen {.,;:/\-+*^%# usw}. Man generiert alle Programme der Länge 1, 2, 3, ... und lässt über jedes so generierte Programm den Compiler zwecks Syntaxprüfung darüberlaufen. Im Fehlerfall verwirft man das Programm, andernfalls fügt man es zur Menge der syntaktisch korrekten Programme hinzu. Ineffizient aber OK.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: nicht-berechenbare Mengen

Beitrag von Skeltek » 19. Sep 2017, 01:27

Das sagte ich doch, wenn auch nicht völlig korrekt formuliert. Die Auswahl wird per Definition von vorn herein eingeschränkt.
Welchen Begriff hätte ich denn verwenden sollen für eine nichtperiodische totalgeordnete Menge an abzählbar unendlich vielen Einzelschritten?
tomS hat geschrieben:
18. Sep 2017, 21:20
Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar.
Würde ich so jetzt nicht stehen lassen. Auch endliche Programme können abzählbar unendlich viele Zustände durchlaufen.
Auf dem PC bekommt man sowas dann nicht zum laufen.
Hier gibt es ein Trade-Off zwischen maximaler Anzahl der Befehle und der Zustände.
Man kann diese Algorithmen auch zustandslos gestalten, indem man statt einer unendlichen Anzahl potentieller Zustände eine unendlich lange Liste an Einzelschritten in den Algorithmus packt. Der Begriff Algorithmus hat erst im Laufe der Hin- und Her-Definition seine Einschränkung auf eine endliche Anzahl an Einzelschritten erhalten. Heute ist die Definition, die sich zur Zeit von Turing entwickelt hat die gebräuchlichste und vom Großteil anerkannte.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: nicht-berechenbare Mengen

Beitrag von tomS » 19. Sep 2017, 08:10

Skeltek hat geschrieben:
19. Sep 2017, 01:27
Das sagte ich doch, wenn auch nicht völlig korrekt formuliert. Die Auswahl wird per Definition von vorn herein eingeschränkt.
Ja, es geht hier einfach um eine Definition.
Skeltek hat geschrieben:
19. Sep 2017, 01:27
tomS hat geschrieben:
18. Sep 2017, 21:20
Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar.
Würde ich so jetzt nicht stehen lassen. Auch endliche Programme können abzählbar unendlich viele Zustände durchlaufen.
Die formale Definition gem. Turing schränkt dies ein. Die Anzahl der internen Zustände der Maschine ist endlich, und da die Maschine halten soll ist auch der Output auf dem (unendlichen) Band endlich.
Skeltek hat geschrieben:
19. Sep 2017, 01:27
Auf dem PC bekommt man sowas dann nicht zum laufen.
Es geht mir nicht um die Ausführung der Programme sondern um deren Generierung.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: nicht-berechenbare Mengen

Beitrag von Skeltek » 19. Sep 2017, 15:36

tomS hat geschrieben:
19. Sep 2017, 08:10
Skeltek hat geschrieben:
19. Sep 2017, 01:27
tomS hat geschrieben:
18. Sep 2017, 21:20
Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar.
Würde ich so jetzt nicht stehen lassen. Auch endliche Programme können abzählbar unendlich viele Zustände durchlaufen.
Die formale Definition gem. Turing schränkt dies ein. Die Anzahl der internen Zustände der Maschine ist endlich, und da die Maschine halten soll ist auch der Output auf dem (unendlichen) Band endlich.
Ja, jetzt bist du aber nicht mehr bei Algorithmus, sondern schon bei endlichen Automaten usw angekommen.
Was ist mit der Berechnung von Pi, der sequentiellen Berechnung aller Nullstellen der riemanschen Zeta-Funktion oder dem einfachen Aufzählen aller natürlichen Zahlen? Hier braucht der Algorithmus in jedem Fall unendlich viele mögliche Zustände - sonst wüsste er ja nicht einmal, wie weit er bereits gezählt hat.
Hier würde ich Algorithmus und Maschinen besser getrennt behandeln.

Was ich sagen wollte war, dass man in diesem Fall sich jegliche Form von Zustandserfassung sparen könnte, indem man einfach eine unendliche Kette/Menge an Einzelschritten formuliert.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: nicht-berechenbare Mengen

Beitrag von tomS » 19. Sep 2017, 16:21

Skeltek hat geschrieben:
19. Sep 2017, 15:36
Ja, jetzt bist du aber nicht mehr bei Algorithmus, sondern schon bei endlichen Automaten usw angekommen.
Was ist mit der Berechnung von Pi, der sequentiellen Berechnung aller Nullstellen der riemanschen Zeta-Funktion oder dem einfachen Aufzählen aller natürlichen Zahlen? Hier braucht der Algorithmus in jedem Fall unendlich viele mögliche Zustände - sonst wüsste er ja nicht einmal, wie weit er bereits gezählt hat.
Nein.

Die Menge der erlaubten inernen Zustände der Turingmaschine bzw. des Algorithmus ist immer endlich; das Alphabet der auf das Band zu schreibenden Symbole ist ebenfalls immer endlich.

Die Ausgabe auf dem Band kann potentiell unendlich sein, und darüber kann auch eine potentiell unendliche Buchführung realisiert werden (man kann zeigen, dass man viele Freiheiten hat, was intern in der Maschine und was extern auf dem Band abgebildet / gespeichert wird, aber die präzise Definition sieht eben ausschließlich das Band. / den Speicher als unendlich vor).

Endliche Automaten können durchaus auf einem unendlichen Speicher operieren. Z.B. kann man für Conway's Game of Life beweisen, dass es Turing-vollständig ist.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Antworten