Abenteuer-Universum

Ich lese gerade ein Buch, da steht, dass es einen Algorithmus gibt, der alle berechenbaren Funktionen auflisten kann. Angenommen das ginge. Das wäre auf jeden Fall eine Liste mit unendlich vielen Spalten (es gäbe ja unendlich viele solcher berechenbaren Funktionen) und Zeilen (es gäbe unendlich viele berechenbare Funktionen mit unendlich vielen Funktionswerten). Dann kann ich doch per Diagonalverfahren eine berechenbare Funktion erschaffen, die nicht in der Liste ist, im Widerspruch zur Annahme. Wie soll so ein Algorithmus funktionieren?

Korrektur: die Liste enthält nur die Funktionen mit Variablen, nicht die Argumente bzw. einzusetzenden Werte.

Das Argument ist recht einfach: gegeben sei ein Satz von Operatoren, d.h. +-*:^ wobei klar ist, dass man auf *^verzichten kann, da dies mittels + darstellbar ist.

Anschließend denke man sich eine Liste F der Form

f(x) = 0
f(x) = 1
...
f(x) = x
f(x) = x+1
...
f(x) = 2*x
...

Man kann jede derartige Liste lexikalisch und damit eindeutig sortieren.

Man kann auch eine Liste S aller endlichen Strings des Alphabets, wiederum sortiert, angeben. Diese Liste kann man sogar mittels eines trivialen Programms über jedem gegebenen Alphabet erzeugen: man erzeugt der Reihe nach alle Strings der Länge Eins, dann der Länge Zwei, dann der Länge Drei usw. Diese Liste S ist offensichtlich abzählbar; sie ist sogar konstruierbar.

Die Liste F der o.g. syntaktisch korrekten Funktionen ist offenbar eine Untermenge der Liste S und damit ebenfalls abzählbar. Man erzeugt nun jeweils einen String aus S, prüft auf syntaktische Korrektheit und fügt den String - wenn letztere vorliegt- der Liste F hinzu.Damit hat man einen Algorithmus, der alle Einträge von F erzeugt, jeden endlichen davon auch in endlicher Zeit.

Bedingung wie nicht-rekursiv, primitiv-rekursiv usw. kann man im Zuge der Prüfung auf syntaktische Korrektheit als zusätzliche Prüfungen implementieren. Statt mit Funktionen f(x) funktioniert dies auch für Computerprogramme; dabei verwendet man bekannte Konstrukte wie DO ... WHILE(...) was zur Äquivalenz derartiger Computerprogramme mit berechenbaren Funktionen führt. Statt in Funktionen darfst du also auch in Computerprogramme denken.

https://de.m.wikipedia.org/wiki/Berechenbarkeit
https://de.m.wikipedia.org/wiki/Primiti ... e_Funktion
https://de.m.wikipedia.org/wiki/%CE%9C-Rekursion
https://de.m.wikipedia.org/wiki/WHILE-Programm
https://de.m.wikipedia.org/wiki/Ackermannfunktion

tomS hat geschrieben: ↑

19. Sep 2018, 00:22

f(x) = 0
f(x) = 1
...
f(x) = x
f(x) = x+1
...
f(x) = 2*x
...

Und nun konstruieren wir eine Funktion: f(diagonal), welche die Liste diagonal durchgeht und jedem Funktionswert eine 1 hinzuaddiert. Diese Funktion wäre doch genauso berechenbar, aber nie in deiner Liste! Es kann also auch keinen derartigen Algorithmus geben, der alle berechenbaren Funktionen auflistet.

Pippen hat geschrieben: ↑

19. Sep 2018, 18:33

tomS hat geschrieben: ↑

19. Sep 2018, 00:22

f(x) = 0
f(x) = 1
...
f(x) = x
f(x) = x+1
...
f(x) = 2*x
...

Und nun konstruieren wir eine Funktion: f(diagonal)

Hallo Pippen,

Du hast aber keine Funktion f(diagonal) - ich erlaube mir, diese mit f("diagonal") anzuschreiben, sondern Du hast nur eine Funktion f(x), d.h. Du hast nicht unendlich viele Spalten, sondern derer lediglich eine.

Den Cantor'schen Diagonalbeweis kannst Du hier nicht anwenden; was man in dieser Situation anwendet sind "Zwei-Tupel" abzählbarer Argumente, von denen man zeigen kann, dass sie, also die Zwei-Tupel, ebenfalls abzählbar sind - Du weisst schon, durch Summenbildung der Komponenten (genauer: der Komponenten-Indizes) mit nachfolgender Anordnung gemäss dieser Komponenten-Summen, wobei man o.E.d.A. zur besseren Veranschaulichung mit der numerisch-kleinsten Komponente anfangen kann - und dann eben die "vollständige Induktion".

Ein Beispiel erklärt mehr als tausend Worte:

Komponentensumme 0: (0,0)
Komponentensumme 1: (0,1), (1,0)
Komponentensumme 2: (0,2), (1,1), (2,0)
Komponentensumme 3: (0,3), (1,2), (2,1), (3,0)
Komponentensumme 4: (0,4), (1,3), (2,2), (3,1), (4,0)
...
Komponentensumme n: (0,n), (1,n-1), (2,n-2), ..., (n-2,2), (n-1,1), (n,0)
Komponentensumme n+1: (0,n+1), (1,n), (2,n-1), ..., (n-2,3), (n-1,2), (n,1), (n+1,0)
...


Freundliche Grüsse, Ralf

Pippen hat geschrieben: ↑

19. Sep 2018, 18:33

Und nun konstruieren wir eine Funktion: f(diagonal), welche die Liste diagonal durchgeht und jedem Funktionswert eine 1 hinzuaddiert. Diese Funktion wäre doch genauso berechenbar, aber nie in deiner Liste! Es kann also auch keinen derartigen Algorithmus geben, der alle berechenbaren Funktionen auflistet.

Meine Idee ist absoluter Standard; kannst du zig-fach nachlesen.

Es handelt sich übrigens um eine Liste; du kannst sie nichts diagonal durchgehen. Und natürlich wäre f(x) = ... +1 in meiner Liste, wenn f(x) = ... in meiner Liste ist.

Genauso könntest du behaupten, ich könnte keine Liste aller Städte hinschreiben.

tomS hat geschrieben: ↑

20. Sep 2018, 00:36

Meine Idee ist absoluter Standard; kannst du zig-fach nachlesen.

Hallo Tom,

Du brauchst Dich da auf keinen Standard zu berufen, Du kannst die Liste ganz konkret wie ich das getan habe mit Zwei-Tupeln und wenn nötig mit vollständiger Induktion konstruieren. Die Induktion ist einfach, denn sei gezeigt, dass die n-Tupel abzählbar sind, so kann man die (n+1)-Tupel als ein 2-Tupel mit dem n-Tupel in der ersten Komponente und der (n+1).-ten Komponente in der 2.Komponente schreiben. Beide Komponenten sind abzählbar, die erste wegen der Induktionsannahme und die zweite per definitionem, somit ist also auch das (n+1)-Tupel abzählbar.

In meinem letzten Beitrag habe ich übrigens die ersten fünfzehn zwei-Tupel "nummeriert".


Freundliche Grüsse, Ralf

Wir nehmen an, es gäbe eine Liste aller berechenbaren Funktionen. Wir definieren einfach jede Funktion dadurch, dass wir ihre Funktionswerte in der Zeile angeben; ist eine Funktion endlich, dann wird einfach der letzte Funktionswert unendlich wiederholt.

Liste:

f₁(1) = 1, f₁(2) = 4, ... [das wäre zB die Quadratfunktion für nat. Zahlen]
f₂(1) = 1, f₂(1) = 1, f₂(1) = 1, ... [das wäre zB die Funktion, die ausschließlich die 1 aufruft und auf 1 abbildet]
f₃(0.5) = 7, f₃(0.55) = 6.7, ...
...

ME gilt: Wir können schon viele berechenbare Funktionen, zB mit reellen Zahlen, gar nicht so notieren und damit auflisten, weil sie überabzählbar sind. Selbst wenn wir das irgendwie könnten, so könnte man diagonalisieren und so eine berechenbare Funktion konstruieren, die in keiner Liste auftauchen kann, oder nicht? Ich verstehe nicht, wie man angesichts dessen alle berechenbaren Funktionen auflisten können soll.

Pippen hat geschrieben: ↑

20. Sep 2018, 03:14

Wir nehmen an, es gäbe eine Liste aller berechenbaren Funktionen. Wir definieren einfach jede Funktion dadurch, dass wir ihre Funktionswerte in der Zeile angeben ...

Es mag sein, dass du damit in Probleme läufst, aber das sind deine Probleme, nicht meine. Ich habe eine andere, viel geschicktere Liste der berechenbaren Funktionen angegeben, nämlich eine Liste der Funktionsvorschriften, nicht der Funktionswerte. Bei meiner Liste greift dein Argument nicht.

Deine Liste ist übrigens auch praktisch völlig nutzlos. Betrachte die einfache Funktion f(x) = x, die ich in jedem Computer trivialerweise implementieren kann, und die offensichtlich berechenbar ist. Nach deiner Definition müsste ich eine unendliche List an Werten angeben.

Es ist ja gerade der Witz von Funktionen, Algorithmen und Computerprogrammen, dass sie ihre Ergebnismenge nicht einfach hinschreiben, sondern eine Funktionsvorschrift zu deren Berechnung angeben. Natürlich gibt es Ergebnismengen, die man nicht hinschreiben kann, nicht mal theoretisch, z.B. die Ergebnismenge der Ackermann-Funktion; trotzdem kann ich die Funktionsvorschrift der Ackermann-Funktion hinschreiben; sie käme sogar in meiner o.g. Liste vor.

Wenn du also argumentieren möchtest, dass es keine Liste der berechenbaren Funktionen geben kann, dann darfst du nicht mit einer ungeschickt konstruierten Liste beginnen. Du müsstest stattdessen beweisen, dass meine Idee zur Formulierung einer geschickten Liste - die Idee aller Logiker, Mathematiker und Informatiker - nicht funktioniert und warum.

Warum ist die Liste, die ich hingeschrieben habe, nicht vollständig?

Pippen hat geschrieben: ↑

20. Sep 2018, 03:14

Wir nehmen an, es gäbe eine Liste aller berechenbaren Funktionen.

Hallo Pippen,

vielleicht ist Dir die Definition der Gleichmächtigkeit nicht exakt geläufig: die Bedingung ist keineswegs, dass alle Abbildungen zwischen 2 Mengen bijektiv sein müssen, sondern es genügt, dass es mindestens eine Abbildung gibt, die bijektiv ist.

Nehmen wir ein einfaches Beispiel: die Menge der natürlichen Zahlen und die Menge der natürlichen Zahl einschliesslich der 0 sind gleichmächtig. Das ist auf den ersten Blick überraschend, da die erste Menge eine eche Teilmenge der zweiten Menge ist.

Nun kann man die Elemente der beiden Mengen versuchen, trivial einander zuzuordnen, also die 1 der 1, die 2 der 2, die 3 der 3 usw. Wenn man das macht, dann bleibt aber in der zweiten Menge die 0 übrig. Diese Abbildung zwischen IN und IN U {0} ist also nicht bijektiv.

Man kann aber eine andere Abbildung finden, z.B. diejenige, die die 1 der 0, die 2 der 1, die 3 der 2 u.s.w. zuordnet. Nun findet jedes Element der ersten Menge genau einen Partner der zweiten Menge, d.h. die beiden Mengen sind gleichmächtig.


Freundliche Grüsse, Ralf

ralfkannenberg hat geschrieben: ↑

20. Sep 2018, 11:02

Pippen hat geschrieben: ↑

20. Sep 2018, 03:14

Wir nehmen an, es gäbe eine Liste aller berechenbaren Funktionen.

Hallo Pippen,

vielleicht ist Dir die Definition der Gleichmächtigkeit nicht exakt geläufig ...

Jedenfalls sind folgende Mengen gleichmächtig, nämlich abzählbar, und können nach Teilmengen absteigend geordnet werden:

Die Menge aller ...
... endlichen Texte über einem endlichen Alphabet
... syntaktisch korrekten Algorithmen gemäß einer Programmiersprache
... berechenbaren Funktionen = μ-rekursiven Funktionen = Turing-mächtige Algorithmen = viele übliche Programmiersprachen
... primitiv-rekursive Funktionen = beweisbar terminierende Algorithmen

Darüberhinaus gibt es auch mächtigere Mengen, z.B.
... alle Funktionen von den natürlichen in die natürlichen Zahlen

Die Menge aller berechenbaren Funktionen kann man nicht durch einen Algorithmus erzeugen, dies wäre ein Gegenbeispiel zum Halteproblem. Die darüber stehenden Mengen kann man dagegen durch einen Algorithmus. Bei den berechenbaren Funktionen besteht das Problem darin, dass kein Algorithmus existiert, der das Halteproblem für alle Funktionen entscheidet.

Pippen hat geschrieben: ↑

18. Sep 2018, 22:04

Ich lese gerade ein Buch, da steht, dass es einen Algorithmus gibt, der alle berechenbaren Funktionen auflisten kann.

Sorry, ich hatte nicht sorgfältig gelesen: was ich skizziere ist die Tatsache, dass die Menge der berechenbaren Funktionen abzählbar ist. Das heißt jedoch nicht, dass auch ein Algorithmus existiert, der diese Menge erzeugt. Im Gegenteil, man kann beweisen dass dieser Algorithmus nicht existiert.

Man kann also keinen Algorithmus angeben, der alle berechenbaren Funktionen erzeugt, obwohl die Menge der berechenbaren Funktionen eine echte Teilmenge der Menge der syntaktisch korrekten Funktionen ist, für die man einen Algorithmus angeben kann. Der Grund ist gerade das Halteproblem, dass es nämlich keinen Algorithmus gibt, der dies für alle syntaktisch korrekten Funktionen entscheiden kann.

Die Aussage “dass es einen Algorithmus gibt, der alle berechenbaren Funktionen auflisten kann” ist falsch.

tomS hat geschrieben: ↑

20. Sep 2018, 07:03

Es mag sein, dass du damit in Probleme läufst, aber das sind deine Probleme, nicht meine. Ich habe eine andere, viel geschicktere Liste der berechenbaren Funktionen angegeben, nämlich eine Liste der Funktionsvorschriften, nicht der Funktionswerte. Bei meiner Liste greift dein Argument nicht.

Ja, deshalb würde ich gern meine Probleme zu deinen machen, in dem ich sage, dass es keinen Unterschied machen darf, ob ich implizit die Funktionsvorschriften angebe oder explizit einfach alle Funktionswerte hinschreibe, um damit die ganze Funktion zu charakterisieren. Das klappt nicht? Denn damit könnte ich meine Liste von unendlich vielen Funktionswerten "durchboxen", die ich diagonalisieren könnte, um damit zu zeigen, dass eben berechenbare Funktionen nicht abzählbar sind.

Meine Liste würde so aussehen:

1, 4, 9, 16, 25, 36, 49, ...
1,3, 5, 67, 3, 7, 89, 3, ...
3, 5, 67, 8, 4, 78, 89, 9, ...
4.5, 6.7, 5, 6.8, 6.1, 55, ...
usw.

Jede Zeile bestünde aus den Funktionswerten und würde eine Funktion eindeutig bezeichnen, zB die erste Zeile die Funktion n², manche Zeile auch mehrere Funktionen, aber egal, jedenfalls kann ich durch Diagonalisierung zeigen, dass es eine berechenbare Funktion gibt, die nicht in dieser Liste ist, in dem ich zu jedem Diagonalelement einfach Eins addiere.

Pippen hat geschrieben: ↑

24. Sep 2018, 22:24

... in dem ich sage, dass es keinen Unterschied machen darf, ob ich implizit die Funktionsvorschriften angebe oder explizit einfach alle Funktionswerte hinschreibe, um damit die ganze Funktion zu charakterisieren.

Es macht aber eben doch einen Unterschied.

Bsp.: die ganzen Zahlen sind offensichtlich abzählbar, wenn du sie in der Reihenfolge 0,+1,-1,+2,-2,+3,-3 ... schreibst; sie erscheinen nicht abzählbar in der Reihenfolge ... -3,-2,-1,0,+1,+2,+3,... Damit ist die letzte Reihenfolge ungeschickt.

Genauso ist es mit deiner Notation der berechenbaren Funktionen. Ich habe gezeigt, dass es eine abzählbare Liste aller endlichen Strings gibt, und dass es eine abzählbare Liste aller syntaktisch korrekten, endlichen Strings gibt. Da jede berechenbaren Funktion durch einen syntaktisch korrekten, endlichen String definiert ist, ist die Menge (nicht Liste - siehe mein Missverständnis oben) aller berechenbaren Funktionen offenbar abzählbar.

Andere Schlussfolgerungen sind dein Problem - sorry.

Pippen hat geschrieben: ↑

24. Sep 2018, 22:24

tomS hat geschrieben: ↑

20. Sep 2018, 07:03

Es mag sein, dass du damit in Probleme läufst, aber das sind deine Probleme, nicht meine. Ich habe eine andere, viel geschicktere Liste der berechenbaren Funktionen angegeben, nämlich eine Liste der Funktionsvorschriften, nicht der Funktionswerte. Bei meiner Liste greift dein Argument nicht.

in dem ich sage, dass es keinen Unterschied machen darf, ob ich implizit die Funktionsvorschriften angebe oder explizit einfach alle Funktionswerte hinschreibe, um damit die ganze Funktion zu charakterisieren. Das klappt nicht? Denn damit könnte ich meine Liste von unendlich vielen Funktionswerten "durchboxen", die ich diagonalisieren könnte, um damit zu zeigen, dass eben berechenbare Funktionen nicht abzählbar sind.

Hallo Pippen,

Du lieferst den Gegenbeweis zu Deiner These gleich selber: es klappt eben nicht, wie Tom Dir ganz konkret gezeigt hat.

Nehmen wir die Identität, also die Funktion f(x) = x.

Die Menge der Funktionen, die Identität darstellen, hat die Mächtigkeit 1, denn es gibt gerade eine davon, wobei ich jetzt auf Besonderheiten wie f(x) = (x*x)/x oder ähnliches nicht eingehen möchte, da man diese im Nullpunkt stetig auf f(x) = x fortsetzen kann.

Wenn Du nun x aus IR wählst, so hast Du also überabzählbar viele Funktionswerte. Die Menge der Funktionswerte ist also überabzählbar unendlich gross, doch die Menge der Funktionen ist endlich vom Wert 1, da es nur eine solche Funktion gibt.


Folglich kann man nicht aus der expliziten Angabe aller Funktionswerte auf die Mächtigkeit der Menge der Funktionen schliessen, sondern lediglich auf die Mächtigkeit der Urbild-Menge, also des Definitionsbereiches der Funktion(en).


Freundliche Grüsse, Ralf

Ja, jetzt verstehe ich es, das Bsp. mit den ganzen Zahlen, die je nach Modellierung mal abzählbar und mal nicht abzählbar wären, macht's gut deutlich.