Du möchtest Mitglied in diesem Forum werden? Bitte setze dich dazu mit der Forenleitung in Verbindung. Ganz unten auf dieser Seite gibt es eine Kontaktmöglichkeit.

nicht-berechenbare Mengen

Mathematische Fragestellungen
Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

nicht-berechenbare Mengen

Beitrag von tomS » 13. Sep 2017, 16:20

Hallo, das ist eine Frage an Ralf.

Im Falle unendlicher Untermengen M der natürlichen Zahlen N kann man Beweise teilweise konstruktiv und teilweise nicht-konstruktiv führen. Konstruktiv bedeutet insbs., dass man die Eigenschaft A, die die Menge M gemäß M = {x: A(x)} definiert, verwendet und dass dieses A(x) für alle natürlichen Zahlen x berechenbar ist, d.h. dass der Algorithmus A(x) für alle x nach endlich vielen Schritten terminiert.

Im Falle der reellen Zahlen existieren nun Beispiele für Mengen, die nicht in diesem Sinne berechenbar sind, und für die die Beweise nicht-konstruktiv verlaufen (z.B. Wohlordnung, mittels Auswahlaxiom, ...). Ein einfaches Beispiel für eine derartige Menge ist die Menge aller nicht-berechenbaren reellen Zahlen. Da es abzählbare viele natürliche Zahlen sowie abzählbar viele Algorithmen A gibt, ist die Ergebnismenge über die Anwendung aller Algorithmen A(x) auf alle natürlichen Zahlen x abzählbar. Da die Menge der reellen Zahken jedoch überabzählbar ist, sind fast alle reellen Zahlen nicht berechenbar.

Frage an Ralf: gibt es auch ein einfaches Beispiel einer nicht-berechenbaren Untermenge der natürlichen Zahlen? Ich denke an die Menge {#A} aller Gödelnummern #A für Algorithmen A(x), die für mindestens eine natürliche Zahl x nicht anhalten. Richtig?
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
ralfkannenberg
Senior-Master
Senior-Master
Beiträge: 665
Registriert: 13. Jan 2017, 10:00

Re: nicht-berechenbare Mengen

Beitrag von ralfkannenberg » 14. Sep 2017, 10:44

tomS hat geschrieben:
13. Sep 2017, 16:20
Hallo, das ist eine Frage an Ralf.
Hallo Tom,

das ist sehr nett, dass Du da an mich denkst, aber ich bin weder Logiker noch Informatiker. Solche Inhalte wurden zu meiner Zeit in der theoretischen Informatik erörtert, die nicht im Lehrplan eines Mathematikers mit Kernwahlfach Informatik stand.


Freundliche Grüsse, Ralf

Skeltek
Ehrenmitglied
Ehrenmitglied
Beiträge: 2920
Registriert: 25. Mär 2008, 23:51

Re: nicht-berechenbare Mengen

Beitrag von Skeltek » 14. Sep 2017, 11:07

Interessante Frage. Du meinst eine Menge, bei welcher nicht bei allen Elementen beurteilt werden kann, ob sie darin liegen oder nicht?
Die plausibelste Erklaerung jedes hinreichend komplizierten Systems ist falsch

Unentscheidbarkeit für Dummies: Dieser Satz ist wahr
oder
Diese Menge hat zwei Elemente: A und B

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 14. Sep 2017, 13:17

Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 14. Sep 2017, 14:18

Bitte an Ralf, hier mitzulesen :-)

Im Extremfall spreche ich von einer Menge, von der kein einziges Element bekannt im Sinne von berechenbar ist.

Nochmal zu meinem Gedankengang: üblicherweise wird eine Menge M definiert als M = {x: A(x)}. x sind dabei irgendwelche Objekte aus einer zuvor gegebenen Menge, hier konkret natürliche Zahlen. A ist eine Eigenschaft; wenn diese für eine Zahl x erfüllt ist, also A(x) wahr ist, dann ist x Element von M.

Um die Menge M zu konstruieren muss ich also alle x durchlaufen, A(x) prüfen und aufgrund von A(x) = wahr (= falsch) entscheiden, dass x ein (kein) Element von M ist.

Dazu muss jedoch A(x) überprüfbar sein, d.h. A(x) muss eine Eigenschaft sein, deren Vorliegen ich mittels eines gegebenen Algorithmus in endlich vielen Schritten prüfen kann. Wenn umgekehrt A(x) nicht in dieser Form überprüfbar ist, dann kann ich nicht entscheiden, ob x zu M gehört.

Ich betrachte nun alle Algorithmen f(x), d.h. Funktionen f auf den natürlichen Zahlen x, die in endlicher Zeit terminieren (und ein Ergebnis y liefern). Wir wissen, dass es Algorithmen f gibt, für die wir das nicht in endlicher Zeit prüfen können (Turingsches Halteproblem). Die Menge M ist dann definiert als

M = {n: n = #f und A(f)}
A(f) = „f(x) terminiert für alle x“

Nun nummeriere ich diese Algorithmen, d.h. ich ordne sie an, z.B. in dem ich den Programmcode alphanumerisch sortiere und so eine abzählbare Liste der Algorithmen erstelle. Jeder natürlichen Zahl wird dann ein Algorithmus f zugeordnet; umgekehrt bezeichne ich mit #f die Position des Algorithmus f in der Liste (das ist einfacher als mit Gödelnummern zu hantieren)

Ein Beispiel könnte folgende Liste sein:
f(x) = 0
f(x) = 1
...
f(x) = x
f(x) = 2x
...

(natürlich terminieren alle diese trivialen Beispiele)

Nun sei A(f) die Eigenschaft, dass f(x) für mindestens eine Eingabe x nicht in endlicher Zeit terminiert. Diese Eigenschaft ist für eine Funktion f sicher entweder wahr oder falsch.

Diese Eigenschaft ist nicht überprüfbar, da ich je f alle, d.h. abzählbar unendlich viele Eingaben x durchlaufen muss. Zum einen kann ich also nie alle Eingaben x prüfen, zum anderen wird der Algorithmus A(f) nicht terminieren, sobald das erste x getestet wird, für das f(x) nicht terminiert.

Ich kann auch das Komplement ~M der Menge M nicht konstruieren, da ich die Negation ~A(f) ebenfalls nicht prüfen kann. ~A(f) ist die Eigenschaft, dass f(x) für alle Eingaben x in endlicher Zeit terminiert. Diese Eigenschaft ist trivialerweise nicht in endlicher Zeit überprüfbar, da ich wiederum abzählbar unendlich viele Eingaben x prüfen muss.

Das Komplement ~M ist teilweise bekannt. Die o.g. Beispiele sind alle Elemente von ~M, d.h. nach der o.g. Sortierung umfasst ~M die Funktionen

~M = {f(x)=0, f(x)=1, …, f(x)=x, f(x)=2x, …}

Die Menge M selbst ist m.M.n. „zum Großteil“ unbekannt, d.h. ich kann immer nur Spezialfälle aus ~M erkennen und für M ausschließen; ich jedoch die verbleibenden Elemente von M nie gesichert erkennen. Spezialfälle wäre z.B. eine triviale, nie abbrechende Rekursion

f(x) = f(f(x))

Meine Frage geht nun dahin, ob es evtl. möglich ist, eine andere Konstruktion für M zu verwenden, so dass tatsächlich alle Elemente unbekannt sind.
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 1493
Registriert: 9. Jul 2010, 04:02

Re: nicht-berechenbare Mengen

Beitrag von Pippen » 14. Sep 2017, 14:40

tomS hat geschrieben:
14. Sep 2017, 14:18
Meine Frage geht nun dahin, ob es evtl. möglich ist, eine andere Konstruktion für M zu verwenden, so dass tatsächlich alle Elemente unbekannt sind.
Was ist mit M := {x|x ist eine natürliche Zahl und so groß, dass sie niemals tatsächlich erfaßt werden kann}. Diese Menge hätte unendlich viele Elemente, nur leider alle per se unbekannt.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 14. Sep 2017, 15:03

was bedeutet "tatsächlich erfasst"?
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 14. Sep 2017, 15:35

Da die Menge aller Turingmaschinen abzählbar unendlich ist, die Menge aller Funktionen f:N ---> N nicht abzählbar unendlich ist, muss es offenbar nicht berechenbare Funktionen der Form
f: N --> N geben. Eine dieser Funktionen ist die Rado-Funktion.
https://www.saarland.de/dokumente/thema ... arkeit.pdf

Ich denke das ist der springende Punkt bei der Geschichte.
Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 14. Sep 2017, 16:11

so wie ich das verstehe ist die Rado-Funktion berechenbar für n<5
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 14. Sep 2017, 17:19

So wie ich es verstanden habe, wurde das für n<5 letztlich durch Ausprobieren herausgefunden und erfüllt somit nicht die Definition von "Berechenbarkeit", da kein endender Algorithmus dafür vorhanden. Ich bin aber nicht ganz sicher.

Wie auch immer ist es ja kein Problem die Bedingung n>=5 hinzuzunehmen, dann hast du eine nicht-berechenbare Zahlenmenge aus natürlichen Zahlen.
Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 14. Sep 2017, 22:38

Für n<5 ist das Ergebnis bekannt, d.h. es existiert ein Beweis, also ein endlicher Algorithmus.
Even though Σ(n) is an uncomputable function, there are some small n for which it is possible to obtain its values and prove that they are correct. It is not hard to show that Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, and with progressively more difficulty it can be shown that Σ(3) = 6 and Σ(4) = 13 (sequence A028444 in the OEIS). Σ(n) has not yet been determined for any instance of n > 4, although lower bounds have been established (see the Known values section below).
In 2016, Adam Yedida and Scott Aaronson obtained the first reasonable explicit upper bound on the minimum n for which Σ(n) is unknowable. To do so they constructed a 7918-state Turing machine whose behavior can never be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (Stationary Ramsey Property).[1][2]
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 1493
Registriert: 9. Jul 2010, 04:02

Re: nicht-berechenbare Mengen

Beitrag von Pippen » 15. Sep 2017, 00:16

tomS hat geschrieben:
14. Sep 2017, 15:03
was bedeutet "tatsächlich erfasst"?
Das man sie irgendwie notieren kann. Der Punkt ist: Die (einzelnen) Elemente dieser Menge wären unbekannt und unverifizierbar. Ist es nicht das, worum es dir geht?

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 15. Sep 2017, 07:02

Pippen hat geschrieben:
15. Sep 2017, 00:16
Die (einzelnen) Elemente dieser Menge wären unbekannt und unverifizierbar. Ist es nicht das, worum es dir geht?
Ja, darum geht es.
Pippen hat geschrieben:
14. Sep 2017, 14:40
Was ist mit M := {x|x ist eine natürliche Zahl und so groß, dass sie niemals tatsächlich erfaßt werden kann}.
Das hat zunächst nichts mit der Größe der Zahl zu tun.

Und meine Frage Bezug sich auf eine präzise Definition. Die Mathematik spricht im Zusammenhang mit Algorithmen, did nach endlich vielen Schritten ein Ergebnis liefern, von berechenbar. Ist es das, was du meinst?
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 15. Sep 2017, 08:10

tomS hat geschrieben:
14. Sep 2017, 22:38
Für n<5 ist das Ergebnis bekannt, d.h. es existiert ein Beweis, also ein endlicher Algorithmus.
Vorsicht, du weisst doch, dass das zwei paar Schuhe sind, zweiseitige Entscheidbarkeit (Berechenbarkeit) und math. Beweis sind verschiedene Dinge.
Man kann manche Dinge mathematisch beweisen, ohne dass ein Algorithmus vorliegt und manchmal kann man auch Berechenbarkeit vorliegen, ohne dass ein mathematischer Beweis vorliegt. Die Goldbach-Eigenschaft ist so ein Fall, wie ich sehe. Und manchmal muss man die Lösung auch erraten ohne sie berechnen zu können und kann dann erst hinterher nachweisen/ausrechnen, ob es stimmt oder nicht.
Aber ich gebe zu, dass ich da noch nicht ganz durchsteige, es genauer anschauen muss und du in sowas besser drinsteckst als ich.

Jedenfalls:

Eine Funktion ist berechenbar, wenn es einen Algorithmus gibt, der für jede natürliche Zahl n nach endlich vielen Schritten den Funktionswert f(n) berechnet.

Und hier ist die Rado-Funktion bb(n) (mit n e N) nicht berechenbar, das wäre sie auch dann noch nicht, wenn Einzelwerte, z.B. bb(1)-bb(4) berechenbar wären (wo ich noch nicht durchsteige, ob sie wirklich berechenbar sind oder stattdessen nur bestimmbar, ist aber wie gesagt eigentlich eh sekundär, wegen dem "jede").

Suchst du nun eine Funktion (eine stärkere Form), wo es sicher für keine natürliche Zahl n einen Algorithmus gibt, der nach endlich vielen Schritten den Funktionswert f(n) berechnet (und wo der Funktionswert dennoch beweisbar existiert)?
Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 15. Sep 2017, 09:31

seeker hat geschrieben:
15. Sep 2017, 08:10
tomS hat geschrieben:
14. Sep 2017, 22:38
Für n<5 ist das Ergebnis bekannt, d.h. es existiert ein Beweis, also ein endlicher Algorithmus.
Vorsicht, du weisst doch, dass das zwei paar Schuhe sind, zweiseitige Entscheidbarkeit (Berechenbarkeit) und math. Beweis sind verschiedene Dinge.
Man kann manche Dinge mathematisch beweisen, ohne dass ein Algorithmus vorliegt und manchmal kann man auch Berechenbarkeit vorliegen, ohne dass ein mathematischer Beweis vorliegt.
I.A. ja, hier im Speziellen nein.

Wenn ich weiß, dass f(3) = 16777216 ist, dann ist es mathematisch äquivalkent, ob ich eine Funktionsvorschrift zur Berechnung habe, oder ob ich die Zahl rate und anschlie0end beweise, dass ich richtig geraten habe. In beiden Fällen führen endlich viele Rechen- bzw. Beweisschritte zu einem eindeutigen Ergebnis (was du meinst sind wohl nicht-konstruktive Beweise; das wäre z.B. der Beweis, dass für jedes n ein fleißiger Biber existiert, jedoch f(n) dennoch nicht berechenbar ist)

seeker hat geschrieben:
15. Sep 2017, 08:10
Eine Funktion ist berechenbar, wenn es einen Algorithmus gibt, der für jede natürliche Zahl n nach endlich vielen Schritten den Funktionswert f(n) berechnet.
Ja.
seeker hat geschrieben:
15. Sep 2017, 08:10
Und hier ist die Rado-Funktion bb(n) (mit n e N) nicht berechenbar, das wäre sie auch dann noch nicht, wenn Einzelwerte, z.B. bb(1)-bb(4) berechenbar wären (wo ich noch nicht durchsteige, ob sie wirklich berechenbar sind oder stattdessen nur bestimmbar, ist aber wie gesagt eigentlich eh sekundär, wegen dem "jede").
Ja.

(ich sehe keinen Unterschied zwischen berechenbar und bestimmbar; es existiert ein "endliches Verfahren", den Wert zu ermitteln)
seeker hat geschrieben:
15. Sep 2017, 08:10
Suchst du nun eine Funktion (eine stärkere Form), wo es sicher für keine natürliche Zahl n einen Algorithmus gibt, der nach endlich vielen Schritten den Funktionswert f(n) berechnet (und wo der Funktionswert dennoch beweisbar existiert)?
Ja.

Nehmen wir wieder die Busy Beaver Funktion f(n). Rado hat m.W.n. gezeigt, dass diese für jedes n existiert. Außerdem hat er gezeigt, dass sie asymptotisch schneller wächst als jede berechenbare Funktion, und damit f(k) für genügend großes k nicht berechenbar sein kann. D.h. man hätte bereits die von mir gewünschte Funktion g(n) auf den natürlichen Zahlen, nämlich g(n) = f(n-k).
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
ralfkannenberg
Senior-Master
Senior-Master
Beiträge: 665
Registriert: 13. Jan 2017, 10:00

Re: nicht-berechenbare Mengen

Beitrag von ralfkannenberg » 15. Sep 2017, 10:13

seeker hat geschrieben:
15. Sep 2017, 08:10
Die Goldbach-Eigenschaft
Hallo seeker,

nur der Vollständigkeit halber: versteht Du hierunter die Eigenschaft, ob man zu einer vorgegebenen geraden Zahl zwei Primzahlen finden kann, deren Summe diese gerade Zahl ergibt ?

Oder verstehtst Du hierunter, dass dies für alle geraden Zahlen grösser als 2 gilt, also die Goldbach'sche Vermutung selber ?


Freundliche Grüsse, Ralf

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 15. Sep 2017, 13:31

@Ralf:
Ich meinte damit folgendes:

Die Goldbachsche Vermutung besagt: Jede gerade Zahl >= 4 lässt sich als Summe zweier Primzahlen darstellen.
(Anm.: Und wenn man die 1 auch zu den Primzahlen hinzunehmen würde, dann könnte man das ">= 4" auch weglassen, weil 1 + 1 = 2.)
Eine Zahl n hat die Goldbach-Eigenschaft, wenn es eine Zahl k < n gibt mit: k und n-k sind Primzahlen

Die Goldbachsche Vermutung ist unbewiesen, also weiß man in dem Sinne nicht, ob alle geraden Zahlen >=4 die Goldbach-Eigenschaft tragen.

Informationstechnisch ist das Problem aber dennoch lösbar, denn dann reduziert es sich auf die Frage: "Gibt es einen Algorithmus, der für jede beliebige gegebene gerade Zahl n >= 4 entscheidet, ob sie die Goldbach-Eigenschaft hat oder nicht?"
Diesen Algorithmus gibt es.

Wir haben hier also etwas , das zwar unbewiesen ist, jedoch in beliebigen Fällen berechenbar.

@Tom:
Ich glaube du hast teilweise Recht:
"Alles Durchprobieren" ist als Algorithmus tatsächlich darstellbar, bei einfachem Raten (ohne alles durchzuprobieren) würde ich das aber nicht unbedingt behaupten, insbesondere nicht, wenn aus einer unendlichen Menge ein Wert durch raten willkürlich gewählt wird.
Bei der Rado-Funktion bis n=4 wurde aber so wie ich das jetzt verstehe das Erstere gemacht und somit also algorithmisch gelöst.
(Wenngleich zu bemerken ist, dass es hier anscheinend i.A. keine Abkürzung zum Durchprobieren gibt, also keine vollständige analytische Lösung des Problems existiert.)
Dass das aus praktischen Gründen für größere n nicht mehr geht ist klar und dass es auch prinzipiell irgendwann nicht mehr gehen kann ergibt sich aus dem Argument, dass die Anzahl der durchzuprobierenden Varianten überexponential mit n wächst, überabzählbar wird, n aber im abzählbaren Bereich bleibt.

Fragt sich dabei nur eines:
tomS hat geschrieben:
15. Sep 2017, 09:31
D.h. man hätte bereits die von mir gewünschte Funktion g(n) auf den natürlichen Zahlen, nämlich g(n) = f(n-k).
Wie groß ist k? Kann man k überhaupt bestimmen?
Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 15. Sep 2017, 13:57

seeker hat geschrieben:
15. Sep 2017, 13:31
Die Goldbachsche Vermutung besagt ...

Wir haben hier also etwas , das zwar unbewiesen ist, jedoch in beliebigen Fällen berechenbar.
Ja, die Goldbachsche Vermutung ist in unserem Kontext insofern irrelevant, als die Menge der geraden Zahlen mit Goldbacheigenwschaft berechenbar ist, da jede Zahl in endlicher Zeit prüfbar ist..
seeker hat geschrieben:
15. Sep 2017, 13:31
Ich glaube du hast teilweise Recht:
"Alles Durchprobieren" ist als Algorithmus tatsächlich darstellbar, bei einfachem Raten (ohne alles durchzuprobieren) würde ich das aber nicht unbedingt behaupten, insbesondere nicht, wenn aus einer unendlichen Menge ein Wert durch raten willkürlich gewählt wird.
Es geht auch nicht ums Raten alleine.

Berechnen
Es geht um die Berechnung von f(x) = y, d.h. um einen endlichen und terminierenden Algorithmus, d.h. z.B. um ein Computerprogramm f, das bei Input x nach endlich vielen Schritten y ausgibt.

Raten und Beweisen
Es geht um die Berechnung von P[f(x) = y] = "wahr", d.h. um einen endlichen und terminierenden Algorithmus oder Beweis, d.h. z.B. um ein Computerprogramm P, das bei Input (f,x,y) nach endlich vielen Schritten "wahr" (oder "falsch") ausgibt.

Dass y geraten wurde ist für die formale Vorgehensweise des Beweisens, also für P irrelevant. Strukturell sind also Berechnen von f(x) = y sowie Beweisen von P[f(x) = y] = "wahr" äquivalent: es existiert ein Algprithmus, der in endlichen Schritten ein Ergebnis liefert und so den Wert y bestätigt.
seeker hat geschrieben:
15. Sep 2017, 13:31
Fragt sich dabei nur eines:
tomS hat geschrieben:
15. Sep 2017, 09:31
D.h. man hätte bereits die von mir gewünschte Funktion g(n) auf den natürlichen Zahlen, nämlich g(n) = f(n-k).
Wie groß ist k? Kann man k überhaupt bestimmen?
Siehe dazu
In 2016, Adam Yedida and Scott Aaronson obtained the first reasonable explicit upper bound on the minimum n for which Σ(n) is unknowable. To do so they constructed a 7918-state Turing machine whose behavior can never be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (Stationary Ramsey Property).
https://en.wikipedia.org/wiki/Busy_beav ... putability
https://www.newscientist.com/article/mg ... -is-wrong/
https://www.scottaaronson.com/blog/?p=2725
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 15. Sep 2017, 14:24

tomS hat geschrieben:
15. Sep 2017, 13:57
Raten und Beweisen
Es geht um die Berechnung von P[f(x) = y] = "wahr", d.h. um einen endlichen und terminierenden Algorithmus oder Beweis, d.h. z.B. um ein Computerprogramm P, das bei Input (f,x,y) nach endlich vielen Schritten "wahr" (oder "falsch") ausgibt.

Dass y geraten wurde ist für die formale Vorgehensweise des Beweisens, also für P irrelevant. Strukturell sind also Berechnen von f(x) = y sowie Beweisen von P[f(x) = y] = "wahr" äquivalent: es existiert ein Algprithmus, der in endlichen Schritten ein Ergebnis liefert und so den Wert y bestätigt.
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.
Wenn du richtig rätst, reicht auch eine einseitige/partielle Entscheidbarkeit aus, wenn nicht, nicht. Du kannst beim willkürlichen Raten nicht im Voraus sicherstellen, dass du richtig rätst.
tomS hat geschrieben:
15. Sep 2017, 13:57
Siehe dazu
In 2016, Adam Yedida and Scott Aaronson obtained the first reasonable explicit upper bound on the minimum n for which Σ(n) is unknowable. To do so they constructed a 7918-state Turing machine whose behavior can never be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (Stationary Ramsey Property).
Das hab ich gelesen aber nicht ganz sicher verstanden. Was meinen die damit? Dass Σ(n), ab der es sicher prinzipiell nicht mehr bestimmbar ist, höchstens bei 7918 liegt oder bei mindestens 7918?
Wenn "höchstens" (ich meine das ist so), dann hätten wir ja das Gesuchte, zumindest ein Beispiel.
Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 15. Sep 2017, 14:30

P.S.: Zusätzlich besteht die Schwierigkeit bei nur einseitig funktionierenden/existierenden Algorithmen, dass dann auch das Verfahren "alles Durchprobieren" dann nicht mehr funktioniert, wenn Möglichkeiten/Eingaben existieren, die falsche Lösungen darstellen.
Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 15. Sep 2017, 15:01

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.
Wenn du richtig rätst, reicht auch eine einseitige/partielle Entscheidbarkeit aus, wenn nicht, nicht. Du kannst beim willkürlichen Raten nicht im Voraus sicherstellen, dass du richtig rätst.
Sehe ich nicht so.

Wenn ich einen Beweis führen kann, dass f(x) = y nach endlich vielen Schritten terminiert, oder wenn ich beweisen kann, dass P[f(x) = y] = "wahr" nach endlich vielen Schritten terminiert, dann ist das völlig äquivalent. Ich kann letzteres mit gegebenen f für jedes x auf alle y=0,1,2,... anwenden und weiß sicher, dass nach endlich vielen Schritten "wahr" ausgegeben wird. Das ist zwar eine ineffizente Methode, y zu berechnen, aber sie ist formal völlig äquivalent zu ersterer. Insbs. kann man beide ineinander überführen.

Rein bzgl. der Frage der Berechenbarkeit sehe ich keinen Unterschied.
seeker hat geschrieben:
15. Sep 2017, 14:24
tomS hat geschrieben:
15. Sep 2017, 13:57
Siehe dazu
In 2016, Adam Yedida and Scott Aaronson obtained the first reasonable explicit upper bound on the minimum n for which Σ(n) is unknowable. To do so they constructed a 7918-state Turing machine whose behavior can never be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (Stationary Ramsey Property).
Das hab ich gelesen aber nicht ganz sicher verstanden. Was meinen die damit? Dass Σ(n), ab der es sicher prinzipiell nicht mehr bestimmbar ist, höchstens bei 7918 liegt oder bei mindestens 7918?
Wenn "höchstens" (ich meine das ist so), dann hätten wir ja das Gesuchte, zumindest ein Beispiel.
Schau mal in die beiden Links:
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.
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 15. Sep 2017, 15:04

seeker hat geschrieben:
15. Sep 2017, 14:30
P.S.: Zusätzlich besteht die Schwierigkeit bei nur einseitig funktionierenden/existierenden Algorithmen, dass dann auch das Verfahren "alles Durchprobieren" dann nicht mehr funktioniert, wenn Möglichkeiten/Eingaben existieren, die falsche Lösungen darstellen.
Das Durchprobieren setzt voraus, dass die Menge entscheidbar ist, d.h. dass für jeden Hypothese P[f(x) = y] das Ergebnis "wahr" oder "falsch" in endlicher Zeit ermittelt werden kann. Dazu muss man jedoch nur einen einmaligen und nicht notwendigerweise konstruktiven Beweis führen.
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Benutzeravatar
seeker
Ehrenmitglied
Ehrenmitglied
Beiträge: 4834
Registriert: 26. Dez 2009, 10:29

Re: nicht-berechenbare Mengen

Beitrag von seeker » 15. Sep 2017, 17:47

tomS hat geschrieben:
15. Sep 2017, 15:01
Wenn ich einen Beweis führen kann, dass f(x) = y nach endlich vielen Schritten terminiert, oder wenn ich beweisen kann, dass P[f(x) = y] = "wahr" nach endlich vielen Schritten terminiert, dann ist das völlig äquivalent. Ich kann letzteres mit gegebenen f für jedes x auf alle y=0,1,2,... anwenden und weiß sicher, dass nach endlich vielen Schritten "wahr" ausgegeben wird. Das ist zwar eine ineffizente Methode, y zu berechnen, aber sie ist formal völlig äquivalent zu ersterer. Insbs. kann man beide ineinander überführen.
Nehmen wir doch einmal an, du hättest einen Algorithmus, wo P[f(x) = y] = "wahr" nach endlich vielen Schritten terminiert, aber P[f(x) = y] = "falsch" nicht terminiert.
Dann kannst du das eben nicht mit gegebenen f für jedes x auf alle y=0,1,2,... anwenden.
D.h. äquivalent ist m.M.n. ein Beweis, dass dass f(x) = y nach endlich vielen Schritten terminiert damit, dass P[f(x) = y] = "wahr" nach endlich vielen Schritten terminiert und dass P[f(x) = y] = "falsch" auch nach endlich vielen Schritten terminiert. Wenn allein P[f(x) = y] = "wahr" nach endlich vielen Schritten terminiert ist das nur die halbe Miete.

Danke für die Links, alles klar!
tomS hat geschrieben:
15. Sep 2017, 15:04
seeker hat geschrieben:
15. Sep 2017, 14:30
P.S.: Zusätzlich besteht die Schwierigkeit bei nur einseitig funktionierenden/existierenden Algorithmen, dass dann auch das Verfahren "alles Durchprobieren" dann nicht mehr funktioniert, wenn Möglichkeiten/Eingaben existieren, die falsche Lösungen darstellen.
Das Durchprobieren setzt voraus, dass die Menge entscheidbar ist, d.h. dass für jeden Hypothese P[f(x) = y] das Ergebnis "wahr" oder "falsch" in endlicher Zeit ermittelt werden kann. Dazu muss man jedoch nur einen einmaligen und nicht notwendigerweise konstruktiven Beweis führen.
Ja. Nur gibt es auch Fälle, wo so ein Beweis noch nicht erbracht werden konnte. In dem Fall steht man irgendwo blöd da: Es könnte dann sein, dass der Algorithmus nie hält (so lange er das noch nie getan hat), aber man weiß es halt nicht, man steckt dann im Halteproblem.
Grüße
seeker


Mache nie eine Theorie zu DEINER Theorie!
Denn tut man das, so verliert man zumindest ein Stück weit seine Unvoreingenommenheit, Objektivität.

Benutzeravatar
tomS
Administrator
Administrator
Beiträge: 8840
Registriert: 19. Nov 2007, 20:29
Wohnort: Nürnberg

Re: nicht-berechenbare Mengen

Beitrag von tomS » 15. Sep 2017, 18:57

Es ging mir ja lediglich um die Aussage, dass eine i) Formel zur Berechnung einer Lösung y sowie ii) ein Beweis, dass eine bestimmte Zahl y eine Lösung darstellt, unter den o.g. Bedingungen, dass der Beweis terminiert, äquivalent sind.
Gruß
Tom

Ἓν οἶδα, ὅτι οὐδὲν οἶδα.

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 1493
Registriert: 9. Jul 2010, 04:02

Re: nicht-berechenbare Mengen

Beitrag von Pippen » 15. Sep 2017, 22:33

berechenbar = beweisbar, berechnet = bewiesen. Oder irre ich mich da?

Antworten

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 4 Gäste