Sowjetisches Nummernschild und Kolmogorov Komplexität

Der Physiker Lev Landau spielte ein mentales Spiel mit sowjetischen Zahlen [ 1 ]. Die Tafeln bestanden aus zwei Zahlen, einem Bindestrich, zwei weiteren Zahlen und einigen Buchstaben.

Spielregel

Sein Spiel bestand darin, mathematische Operatoren auf Zahlen auf beiden Seiten des Strichs anzuwenden, damit der Strich durch ein Gleichheitszeichen ersetzt werden konnte. Wenn Sie beispielsweise das Nummernschild 44-74 nehmen, ist eine der Lösungen

4! + 4 = 7 * 4

Bitte beachten Sie, dass wir Operatoren wie ! , + und * , aber ohne Zahlen hinzuzufügen.

Gibt es für jedes mögliche Nummernschild eine Lösung? Dies hängt davon ab, welche Operatoren Sie verwenden dürfen.

Sie können das Spiel trivialisieren, indem Sie die Bruchteiloperation {x} auf beide Seiten anwenden, da der Bruchteil einer Ganzzahl Null ist. Sie können den Bruchteilbetreiber mit der Begründung verbieten, dass dies eindeutig keine mathematische Operation der High School ist, oder sie einfach verbieten, weil dies das Spiel uninteressant macht.

Die Übersetzung wurde von EDISON Software unterstützt , die in vielversprechende Startups investiert und verschiedene Cloud-Services entwickelt .

One-Stop-Lösung

Es stellt sich heraus, dass es eine universelle Lösung gibt, beginnend mit der Beobachtung, dass

√ (n + 1) = sec arctan √ n.

Wenn eine Seite größer als die andere ist, ergibt die obige Formel eine sofortige Lösung. Zum Beispiel wird eine Lösung für ein Kennzeichen 89-88 sein

√89 = sec arctan√88.

Wenn der Unterschied größer ist, kann die Formel wiederholt angewendet werden. Zum Beispiel könnten wir die Formel zweimal anwenden, um zu erhalten

√ (n + 2) = sec arctan√ (n + 1) = sec arctan sec arctan√ n

und daher ist eine mögliche Lösung für 35-37

sec arctan sec arctan √35 = √37.

Kolmogorov Komplexität

Da eine Lösung immer möglich ist, können wir das Spiel interessanter machen, indem wir die einfachste Lösung finden. Wir haben ein intuitives Verständnis dafür, was dies bedeutet. Mit unserem Beispiel 44-74 die erste Lösung

4! + 4 = 7 * 4

einfacher als universelle Lösung

sec arctan sec arctan ... √44 = √74

Dies würde den 30-fachen Einsatz von Sekanten und Arkustangens erfordern.

Die Kolmogorov-Komplexität eines Objekts ist die Länge des kürzesten Computerprogramms zum Erstellen eines Objekts. Wir könnten die Kolmogorov-Komplexität der Funktionen berechnen, die auf die Zahlen auf jeder Seite angewendet werden, um zu messen, wie komplex die Lösung ist.

Um dies herauszufinden, müssen wir angeben, welche Programmiersprache wir haben, und es ist nicht so einfach, wie es scheint. Wenn wir die mathematische Notation als Programmiersprache betrachten, wollen wir zählen! wie ein Charakter und arctan wie 6 Zeichen? Das scheint nicht richtig zu sein. Wenn wir "arctan" als "atn" schreiben würden, würden wir weniger Zeichen verwenden, ohne eine andere Lösung zu erstellen.

Komplexität des Python-Codes

Um die Dinge objektiver zu gestalten, könnten wir die Länge realer Computerprogramme berücksichtigen, anstatt die mathematische Notation als Programmiersprache darzustellen. Nehmen wir an, wir haben Python gewählt. Dann sind hier einige Funktionen, die unsere beiden Kennzeichenlösungen 44-74 berechnen.

from math import sqrt, cos, atan def f(): sec = lambda x: 1/cos(x) y = sqrt(44) for _ in range(30): y = sec(atan(y)) return y def g(): return sqrt(77) 

Wir könnten die Komplexität unserer Funktionen f und g messen, indem wir die Anzahl der Zeichen in jedem zählen. Aber es gibt immer noch Schwierigkeiten.

Was ist mit Importen? Seine Länge muss mit f rechnen, da alle importierten Anweisungen verwendet werden, g jedoch eine kürzere Anweisung verwendet, die nur sqrt importiert. Täuschen wir im Grunde genommen sogar den Import einer Bibliothek?

Darüber hinaus liefern die beiden oben genannten Funktionen aufgrund der begrenzten Genauigkeit nicht genau das gleiche Ergebnis. Wir können uns vorstellen, dass unsere importierten Funktionen unendlich genau sind, aber dann verwenden wir nicht Python, sondern eine idealisierte Version von Python.

Was ist mit der Schleife? Dies führte neue Zahlen, 3 und 0, ein und verstößt daher gegen die Regeln des Landau-Spiels. Sollen wir uns also abrollen, bevor wir die Komplexität berechnen?

Gedankenexperiment

Kolmogorovs Komplexität ist ein sehr nützliches Konzept, aber es ist eher ein mentales Experiment als das, was Sie in der Praxis berechnen können. Wir können uns das kürzeste Programm vorstellen, um etwas zu berechnen, aber wir wissen selten, dass wir wirklich ein solches Programm gefunden haben. In der Praxis können wir nur die Obergrenzen kennen.

Theoretisch können Sie alle Turing-Maschinen einer bestimmten Länge oder alle Python-Programme einer bestimmten Länge auflisten und die kürzeste finden, die diese Aufgabe ausführt. Die Liste wächst jedoch exponentiell mit zunehmender Länge.

Es ist jedoch möglich, die Dauer bestimmter Programme zu berechnen, wenn wir uns mit einigen der oben genannten Schwierigkeiten befassen. Wir könnten Landau zu einem Spiel für zwei machen, indem wir sehen, wer in einer festgelegten Zeit eine einfachere Lösung anbieten kann.

Zurück nach Landau

Wenn wir Sinus und Grad in unserer Gruppe von Operatoren zulassen, dann ist B.S. Gorobets ist eine universelle Lösung. Für n ≥ 6 ist n! ein Vielfaches von 360 und so

sin (n!) ° = 0.

Und wenn n kleiner als 6 ist, beginnt seine zweistellige Darstellung bei Null, sodass wir die Zahlen multiplizieren können, um Null zu erhalten.

Wenn wir transzendentale Funktionen verbieten, blockieren wir den Gorobets-Trick und haben Funktionen, deren Länge wir objektiv in einer Programmiersprache messen können.