Jemand in einer Diskussion brachte vor, dass (er meint) es zumindest eine ununterbrochene Anzahl von Strategien geben kann, um sich einem bestimmten Problem zu nähern. Das spezifische Problem waren Handelsstrategien (nicht Algorithmen, sondern Strategien), aber ich denke, das ist neben dem Punkt für meine Frage.
Dies brachte mich dazu, über die Kardinalität der Algorithmen nachzudenken. Ich habe ein bisschen gesucht, aber nichts gefunden. Ich habe gedacht, dass es unmöglich ist, unzählige Algorithmen zu haben, da Turing-Maschinen mit einem endlichen Satz von Buchstaben arbeiten und das Band indexierbar und somit zählbar sein muss. Meine Mengenlehre ist zugegebenermaßen verrostet, daher bin ich mir nicht sicher, ob meine Überlegungen stimmen und ich würde es wahrscheinlich nicht beweisen können, aber es ist ein interessanter Gedanke.
Was ist die Kardinalität der Algorithmen?
Antworten:
Ein Algorithmus wird informell als eine endliche Folge von schriftlichen Anweisungen zum Ausführen einer Aufgabe beschrieben. Genauer gesagt, sie werden als Turing-Maschinen bezeichnet, obwohl man sie genauso gut als Computerprogramme bezeichnen kann.
Der genaue Formalismus, den Sie verwenden, spielt keine Rolle, aber der grundlegende Punkt ist, dass jeder Algorithmus als endliche Folge von Zeichen aufgeschrieben werden kann, wobei die Zeichen aus einer endlichen Menge ausgewählt werden, z. B. römischen Buchstaben, ASCII oder Nullen und Einsen. Nehmen wir der Einfachheit halber Nullen und Einsen an. Jede Folge von Nullen und Einsen ist nur eine natürliche Zahl, die binär geschrieben ist. Das heißt, es gibt höchstens eine zählbare Unendlichkeit von Algorithmen, da jeder Algorithmus als natürliche Zahl dargestellt werden kann.
Für eine vollständige Gutschrift sollten Sie sich Sorgen machen, dass einige natürliche Zahlen möglicherweise keine gültigen Programme codieren. Daher gibt es möglicherweise weniger Algorithmen als natürliche Zahlen. (Für Bonusguthaben, können Sie auch fragen, ob es möglich ist , dass zwei verschiedene natürliche Zahlen den gleichen Algorithmus darstellen.) Allerdings
print 1
,print 2
,print 3
und so weiter sind alle Algorithmen und alle verschieden, so dass es zumindest abzählbar unendlich viele Algorithmen.Wir schließen daraus, dass die Menge der Algorithmen unendlich ist.
quelle
Die Menge der Algorithmen ist unendlich. Dies liegt daran, dass jeder Algorithmus eine endliche Beschreibung hat, etwa als Turing-Maschine.
Die Tatsache, dass ein Algorithmus eine endliche Beschreibung hat, ermöglicht es uns, einen Algorithmus in einen anderen einzugeben, und dies ist die Grundlage der Berechenbarkeitstheorie. So können wir zum Beispiel das Halteproblem formulieren.
quelle
"Continuum" soll wahrscheinlich die reellen Zahlen bedeuten ... "mindestens" zusammen mit diesem Wort zu verwenden, ist absurd übertrieben. Ein bisschen Zunge im Mund zu sein: Zählbar unendlich ist ziemlich groß, aber unzählbar unendlich ist ... größer als groß. Sehr viel mehr. Unfassbar.
Also lasst uns das aus dem Fenster werfen. Zu sehen, mit welcher Art von Unendlichkeit wir es zu tun haben, ist kinderleicht (und intuitiv, auch wenn Ihr Freund noch nie von theoretischer Informatik gehört hat):
Ich weiß nicht, was dein Freund mit "Strategie" meint. Ich nehme an, er meint etwas, das einem Algorithmus ähnelt, aber nicht detailliert genug formuliert ist, um es in einen Computer zu hacken. Oder was hängt irgendwie von der menschlichen "Intuition" während der Hinrichtung ab? Wenn ja, dann sind dies nur irrelevante Details. Die Menschheit hat noch keine Beschreibung von Prozessen gefunden, die leistungsfähiger oder umfangreicher sind als "Algorithmen" in dem Sinne, wie wir sie in CS verwenden.
quelle
Siehe Gödel-Nummerierung , es ist eine grundlegende Tatsache in der Informatik, dass Algorithmen ebenso abzählbar sind wie rekursiv aufzählbare Mengen.
Da Algorithmen abzählbar sind, kann leicht gezeigt werden, dass es keinen Algorithmus gibt, mit dem jede Menge in einem formalen System überprüft werden kann (ordnen Sie einem Problem einen Wahrheitswert zu). Dies wäre äquivalent dazu, jeder Funktion einen Algorithmus zuzuweisen, der die Menge der Probleme auf boolesche Werte abbildet. Die Menge dieser Funktionen ist jedoch unzählbar (trivial von derselben Kardinalität wie die Potenzmenge der Menge von Problemen, daher unzählbar).
Ich hoffe, dies gibt einen Anhaltspunkt dafür, warum Algorithmen "weniger leistungsfähig" als jede andere Funktion sein müssen, eine so abzählbare (ignorieren wir hier die Kontinuumshypothese).
quelle
Wenn man nicht mit der Anforderung beginnt, dass eine Strategie mit einem Algorithmus implementierbar sein muss, und reale Diskretisierungseffekte ignoriert, könnte man zum Beispiel Folgendes als parametrisierte Handelsstrategie akzeptieren:
quelle
Wenn wir uns Algorithmen als Computerprogramme vorstellen, die in Binärform * geschrieben sind, dann ist die Anzahl der Algorithmen die Anzahl der (ganzzahligen) Binärzahlen. Die Kardinalität von Algorithmen ist also die Kardinalität der ganzen Zahlen.
* Ein Beweis, dass Turing-Maschinen alle Algorithmen ausführen können und dass Computer alle Programm-Turing-Maschinen ausführen können, würde diese Antwort unnötig lang machen. Ersteres hängt möglicherweise von der Definition eines Algorithmus ab, aber ich glaube nicht, dass Sie unberechenbare Handelsstrategien anwenden.
quelle
Die anderen Antworten haben bereits erklärt, dass im Standardmodell der Berechnung (Turing-Maschinen, Lambda-Berechnung usw.) die Menge der Algorithmen unzählbar unendlich ist.
Es gibt jedoch auch andere theoretische Berechnungsmodelle, bei denen die Anzahl der Algorithmen unzählige ist. Zum Beispiel haben Blum-Shub-Smale-Maschinen einen unzähligen Befehlssatz 1 , so dass ihr Satz von Algorithmen ebenfalls unzählig ist.
1 Um genau zu sein, der Befehlssatz selbst ist endlich, aber er wird mit einem unzähligen Satz (den rationalen Funktionen) parametrisiert.
quelle
Bei einer bestimmten Größe gibt es endlich viele Turingmaschinen und es gibt zählbar viele Größen. Eine abzählbare Menge von Zahlen, die endlich sind, ist abzählbar. Die Größe des Alphabets ist ein Faktor für die Anzahl der Turing-Maschinen, die Größe des Bands jedoch nicht. Wenn das Alphabet zählbar viele Zeichen enthalten würde, gäbe es unzählig viele Maschinen (jede reelle Zahl könnte als Folge von Symbolen codiert werden).
quelle