El físico Lev Landau jugó un juego mental con números soviéticos [
1 ]. Las tabletas tenían la forma de dos números, un guión, dos números más y algunas letras.
Reglas del juego
Su juego consistía en aplicar operadores matemáticos a los números a ambos lados del tablero para que el tablero pudiera reemplazarse con un signo igual. Por ejemplo, si toma la matrícula 44-74, una de las soluciones sería
4! + 4 = 7 * 4Tenga en cuenta que podemos insertar operadores como
! ,
+ y
* , pero sin sumar números.
¿Hay una solución para cada placa posible? Depende de los operadores que permita usar.
Puede trivializar el juego aplicando la operación de parte fraccionaria {x} a ambos lados, ya que la parte fraccionaria de un entero es cero. Puede prohibir el operador de la parte fraccional alegando que esto claramente no es una operación matemática de la escuela secundaria, o simplemente prohibirlo porque hace que el juego no sea interesante.
La traducción fue respaldada por EDISON Software , que invierte en nuevas empresas prometedoras , y también desarrolla varios servicios en la nube .
Solución integral
Resulta que hay una solución universal, comenzando con la observación de que
√ (n + 1) = sec arctan √ n.
Si un lado es uno más grande que el otro, la fórmula anterior brinda una solución inmediata. Por ejemplo, una solución para una matrícula número 89-88 será
√89 = sec arctan√88.
Si la diferencia es mayor, la fórmula se puede aplicar repetidamente. Por ejemplo, podríamos aplicar la fórmula dos veces para obtener
√ (n + 2) = sec arctan√ (n + 1) = sec arctan sec arctan√ n
y por lo tanto, una posible solución para 35-37 es
sec arctan sec arctan √35 = √37.
Complejidad de Kolmogorov
Dado que siempre es posible una solución, podemos hacer que el juego sea más interesante al encontrar la solución más simple. Tenemos una comprensión intuitiva de lo que esto significa. Con nuestro ejemplo 44-74, la primera solución
4! + 4 = 7 * 4
solución más simple que universal
sec arctan sec arctan ... √44 = √74
lo que requeriría el uso de secantes y arcotangentes 30 veces.
La complejidad de Kolmogorov de un objeto es la longitud del programa de computadora más corto para crear un objeto. Podríamos calcular la complejidad de Kolmogorov de las funciones aplicadas a los números en cada lado para medir qué tan compleja es la solución.
Para averiguarlo, necesitamos indicar qué lenguaje de programación tenemos, y no es tan simple como parece. Si pensamos en la notación matemática como un lenguaje de programación, ¿queremos contar? como un personaje y arctan como 6 personajes? Esto no parece correcto. Si escribiéramos "arctan" como "atn", usaríamos menos caracteres sin crear otra solución.
Complejidad del código Python
Para hacer las cosas más objetivas, podríamos considerar la longitud de los programas informáticos reales, en lugar de presentar la notación matemática como un lenguaje de programación. Digamos que elegimos Python. Luego, aquí hay un par de funciones que calculan nuestras dos soluciones de matrícula 44-74.
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)
Podríamos medir la complejidad de nuestras funciones f y g contando el número de caracteres en cada una. Pero todavía hay dificultades.
¿Qué pasa con las importaciones? Su longitud debe contar con f porque usa todas las declaraciones importadas, pero g usa una declaración más corta que solo importó sqrt. Más fundamentalmente, ¿estamos engañando incluso importando una biblioteca?
Además, las dos funciones mencionadas anteriormente no dan exactamente el mismo resultado debido a la precisión limitada. Podemos imaginar que nuestras funciones importadas son infinitamente precisas, pero en realidad no usamos Python, sino una versión idealizada de Python.
¿Qué pasa con el bucle? Esto introdujo nuevos números, 3 y 0, y por lo tanto viola las reglas del juego Landau. Entonces, ¿deberíamos desenrollarnos antes de calcular la complejidad?
Experimento de pensamiento
La complejidad de Kolmogorov es un concepto muy útil, pero es más un experimento mental que lo que puedes calcular en la práctica. Podemos imaginar el programa más corto para calcular algo, pero rara vez sabemos que realmente encontramos un programa así. Todo lo que podemos saber en la práctica son los límites superiores.
Teóricamente, puede enumerar todas las máquinas de Turing de una longitud determinada o todos los programas de Python de una longitud determinada y encontrar el más corto que realice esta tarea, pero la lista crece exponencialmente a medida que aumenta la longitud.
Sin embargo, es posible calcular la duración de programas específicos si estamos lidiando con algunas de las dificultades mencionadas anteriormente. Podríamos hacer de Landau un juego para dos al ver quién puede ofrecer una solución más simple en un período de tiempo fijo.
De vuelta a Landau
Si permitimos seno y grado en nuestro conjunto de operadores, entonces B.S. Gorobets es una solución universal. Para n ≥ 6, n! un múltiplo de 360, y así
sin (n!) ° = 0.
Y si n es menor que 6, su representación de dos dígitos comienza desde cero, por lo que podemos multiplicar los números para obtener cero.
Si prohibimos las funciones trascendentales, bloqueamos el truco de Gorobets y tenemos funciones cuya longitud podemos medir objetivamente en un lenguaje de programación.