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.

Liste berechenbarer Funktionen

Mathematische Fragestellungen
Antworten
Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 1810
Registriert: 9. Jul 2010, 04:02

Liste berechenbarer Funktionen

Beitrag von Pippen » 18. Sep 2018, 22:04

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?

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

Re: Liste berechenbarer Funktionen

Beitrag von tomS » 19. Sep 2018, 00:22

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
Gruß
Tom

Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

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

Re: Liste berechenbarer Funktionen

Beitrag von Pippen » 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), 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.

Benutzeravatar
ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 1872
Registriert: 13. Jan 2017, 10:00

Re: Liste berechenbarer Funktionen

Beitrag von ralfkannenberg » 19. Sep 2018, 20:48

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

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

Re: Liste berechenbarer Funktionen

Beitrag von tomS » 20. Sep 2018, 00:36

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.
Gruß
Tom

Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

Benutzeravatar
ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 1872
Registriert: 13. Jan 2017, 10:00

Re: Liste berechenbarer Funktionen

Beitrag von ralfkannenberg » 20. Sep 2018, 01:12

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

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

Re: Liste berechenbarer Funktionen

Beitrag von Pippen » 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; ist eine Funktion endlich, dann wird einfach der letzte Funktionswert unendlich wiederholt.

Liste:

f1(1) = 1, f1(2) = 4, ... [das wäre zB die Quadratfunktion für nat. Zahlen]
f2(1) = 1, f2(1) = 1, f2(1) = 1, ... [das wäre zB die Funktion, die ausschließlich die 1 aufruft und auf 1 abbildet]
f3(0.5) = 7, f3(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.

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

Re: Liste berechenbarer Funktionen

Beitrag von tomS » 20. Sep 2018, 07:03

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?
Gruß
Tom

Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

Benutzeravatar
ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 1872
Registriert: 13. Jan 2017, 10:00

Re: Liste berechenbarer Funktionen

Beitrag von ralfkannenberg » 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: 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

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

Re: Liste berechenbarer Funktionen

Beitrag von tomS » 20. Sep 2018, 14:34

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.
Gruß
Tom

Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

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

Re: Liste berechenbarer Funktionen

Beitrag von tomS » 21. Sep 2018, 08:16

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.
Gruß
Tom

Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

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

Re: Liste berechenbarer Funktionen

Beitrag von Pippen » 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.
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.

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

Re: Liste berechenbarer Funktionen

Beitrag von tomS » 24. Sep 2018, 22:44

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.
Gruß
Tom

Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

Benutzeravatar
ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 1872
Registriert: 13. Jan 2017, 10:00

Re: Liste berechenbarer Funktionen

Beitrag von ralfkannenberg » 25. Sep 2018, 00:38

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

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

Re: Liste berechenbarer Funktionen

Beitrag von Pippen » 28. Sep 2018, 23:18

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.

Antworten