Le physicien Lev Landau a joué un jeu mental avec les chiffres soviétiques [
1 ]. Les tablettes se présentaient sous la forme de deux chiffres, un tiret, deux autres chiffres et quelques lettres.
Règles du jeu
Son jeu consistait à appliquer des opérateurs mathématiques aux nombres de chaque côté du tiret afin que le tiret puisse être remplacé par un signe égal. Par exemple, si vous prenez la plaque d'immatriculation 44-74, l'une des solutions serait
4! + 4 = 7 * 4Veuillez noter que nous pouvons insérer des opérateurs tels que
! ,
+ et
* , mais sans addition de chiffres.
Existe-t-il une solution pour chaque plaque d'immatriculation possible? Cela dépend des opérateurs que vous autorisez à utiliser.
Vous pouvez banaliser le jeu en appliquant l'opération de partie fractionnaire {x} aux deux côtés, car la partie fractionnaire d'un entier est nulle. Vous pouvez interdire l'opérateur de partie fractionnaire au motif qu'il ne s'agit clairement pas d'une opération mathématique du lycée, ou simplement l'interdire car cela rend le jeu sans intérêt.
La traduction a été prise en charge par EDISON Software , qui investit dans des startups prometteuses et développe également divers services cloud .
Solution unique
Il s'avère qu'il existe une solution universelle, à commencer par l'observation que
√ (n + 1) = sec arctan √ n.
Si un côté est plus grand que l'autre, la formule ci-dessus donne une solution immédiate. Par exemple, une solution pour une plaque d'immatriculation numéro 89-88 sera
√89 = sec arctan√88.
Si la différence est plus grande, la formule peut être appliquée à plusieurs reprises. Par exemple, nous pourrions appliquer la formule deux fois pour obtenir
√ (n + 2) = sec arctan√ (n + 1) = sec arctan sec arctan√ n
et donc une solution possible pour 35-37 est
sec arctan sec arctan √35 = √37.
Complexité de Kolmogorov
Étant donné qu'une solution est toujours possible, nous pouvons rendre le jeu plus intéressant en trouvant la solution la plus simple. Nous avons une compréhension intuitive de ce que cela signifie. Avec notre exemple 44-74, la première solution
4! + 4 = 7 * 4
solution plus simple que universelle
sec arctan sec arctan ... √44 = √74
ce qui nécessiterait l'utilisation de sécants et d'arctangents 30 fois.
La complexité de Kolmogorov d'un objet est la longueur du programme informatique le plus court pour créer un objet. Nous pourrions calculer la complexité de Kolmogorov des fonctions appliquées aux nombres de chaque côté pour mesurer la complexité de la solution.
Pour le savoir, nous devons indiquer quel langage de programmation nous avons, et ce n'est pas aussi simple qu'il y paraît. Si nous considérons la notation mathématique comme un langage de programmation, voulons-nous compter! comme un personnage et arctan comme 6 personnages? Cela ne semble pas correct. Si nous écrivions «arctan» comme «atn», nous utiliserions moins de caractères sans créer une autre solution.
Complexité du code Python
Pour rendre les choses plus objectives, nous pourrions considérer la longueur des vrais programmes informatiques, plutôt que de présenter la notation mathématique comme un langage de programmation. Disons que nous avons choisi Python. Voici ensuite quelques fonctions que nos deux solutions de plaques d'immatriculation 44-74 calculent.
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)
Nous pourrions mesurer la complexité de nos fonctions f et g en comptant le nombre de caractères dans chacune. Mais il reste des difficultés.
Et les importations? Sa longueur doit compter avec f car il utilise toutes les instructions importées, mais g a utilisé une instruction plus courte qui n'a importé que sqrt. Plus fondamentalement, trompons-nous même l'importation d'une bibliothèque?
De plus, les deux fonctions susmentionnées ne donnent pas exactement le même résultat en raison d'une précision limitée. Nous pouvons imaginer que nos fonctions importées sont infiniment précises, mais alors nous n'utilisons pas réellement Python, mais plutôt une version idéalisée de Python.
Et la boucle? Cela a introduit de nouveaux numéros, 3 et 0, et viole donc les règles du jeu Landau. Faut-il donc dérouler avant de calculer la complexité?
Expérience de pensée
La complexité de Kolmogorov est un concept très utile, mais c'est plus une expérience mentale que ce que vous pouvez calculer dans la pratique. Nous pouvons imaginer le programme le plus court pour calculer quelque chose, mais nous savons rarement que nous avons vraiment trouvé un tel programme. Tout ce que nous pouvons savoir en pratique, ce sont les limites supérieures.
Théoriquement, vous pouvez répertorier toutes les machines Turing d'une longueur donnée ou tous les programmes Python d'une longueur donnée et trouver le plus court qui effectue cette tâche, mais la liste s'allonge de façon exponentielle avec l'augmentation de la longueur.
Cependant, il est possible de calculer la durée de programmes spécifiques si nous traitons certaines des difficultés mentionnées ci-dessus. Nous pourrions faire de Landau un jeu pour deux en voyant qui peut offrir une solution plus simple dans un laps de temps fixe.
Retour à Landau
Si nous autorisons le sinus et le degré dans notre ensemble d'opérateurs, alors B.S. Gorobets est une solution universelle. Pour n ≥ 6, n! un multiple de 360, et ainsi
sin (n!) ° = 0.
Et si n est inférieur à 6, sa représentation à deux chiffres commence à zéro, nous pouvons donc multiplier les nombres pour obtenir zéro.
Si nous interdisons les fonctions transcendantales, nous bloquons l'astuce Gorobets et nous avons des fonctions dont nous pouvons mesurer objectivement la longueur dans un langage de programmation.