O físico Lev Landau jogou um jogo mental com números soviéticos [
1 ]. Os comprimidos estavam na forma de dois números, um hífen, mais dois números e algumas letras.
Regras do jogo
Seu jogo era aplicar operadores matemáticos a números dos dois lados do painel, para que o painel pudesse ser substituído por um sinal de igual. Por exemplo, se você pegar a chapa de matrícula 44-74, uma das soluções seria
4! + 4 = 7 * 4Observe que podemos inserir operadores como
! ,
+ e
* , mas sem adicionar números.
Existe uma solução para todas as placas possíveis? Depende de quais operadores você permite usar.
Você pode banalizar o jogo aplicando a operação da parte fracionária {x} nos dois lados, pois a parte fracionária de um número inteiro é zero. Você pode proibir o operador de parte fracionária com o argumento de que essa claramente não é uma operação matemática do ensino médio ou simplesmente proibi-la porque torna o jogo desinteressante.
A tradução foi apoiada pela EDISON Software , que investe em startups promissoras e também desenvolve vários serviços em nuvem .
Solução de parada
Acontece que existe uma solução universal, começando pela observação de que
√ (n + 1) = seg arctan √ n.
Se um lado é maior que o outro, a fórmula acima fornece uma solução imediata. Por exemplo, uma solução para uma placa número 89-88 será
√89 = seg arctan√88.
Se a diferença for maior, a fórmula pode ser aplicada repetidamente. Por exemplo, podemos aplicar a fórmula duas vezes para obter
√ (n + 2) = seg arctan√ (n + 1) = seg arctan seg arctan√ n
e, portanto, uma possível solução para 35-37 é
sec arctan sec arctan √35 = √37.
Complexidade de Kolmogorov
Dado que uma solução é sempre possível, podemos tornar o jogo mais interessante, encontrando a solução mais simples. Temos uma compreensão intuitiva do que isso significa. No nosso exemplo 44-74, a primeira solução
4! + 4 = 7 * 4
solução mais simples que universal
sec arctan sec arctan ... √44 = √74
o que exigiria o uso de secantes e arco-tangentes 30 vezes.
A complexidade de Kolmogorov de um objeto é o tamanho do menor programa de computador para criar um objeto. Poderíamos calcular a complexidade de Kolmogorov das funções aplicadas aos números de cada lado para medir a complexidade da solução.
Para descobrir, precisamos indicar qual linguagem de programação temos e não é tão simples quanto parece. Se pensarmos na notação matemática como uma linguagem de programação, queremos contar! como um personagem e arctan como 6 caracteres? Isso não parece certo. Se escrevêssemos “arctan” como “atn”, usaríamos menos caracteres sem criar outra solução.
Complexidade do código Python
Para tornar as coisas mais objetivas, poderíamos considerar a duração de programas de computador reais, em vez de apresentar a notação matemática como uma linguagem de programação. Digamos que escolhemos Python. Aqui estão algumas funções que nossas duas soluções de placas 44-74 calculam.
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)
Poderíamos medir a complexidade de nossas funções feeg contando o número de caracteres em cada uma. Mas ainda existem dificuldades.
E as importações? Seu comprimento deve contar com f porque usa todas as instruções importadas, mas g usou uma declaração mais curta que apenas importou sqrt. Mais fundamentalmente, estamos enganando até importando uma biblioteca?
Além disso, as duas funções mencionadas acima não fornecem exatamente o mesmo resultado devido à precisão limitada. Podemos imaginar que nossas funções importadas são infinitamente precisas, mas, na verdade, não usamos o Python, mas uma versão idealizada do Python.
E o laço? Isso introduziu novos números, 3 e 0, e, portanto, viola as regras do jogo Landau. Então, devemos desenrolar antes de calcular a complexidade?
Experiência de pensamento
A complexidade de Kolmogorov é um conceito muito útil, mas é mais um experimento mental do que você pode calcular na prática. Podemos imaginar o programa mais curto para calcular algo, mas raramente sabemos que realmente encontramos esse programa. Tudo o que podemos saber na prática são os limites superiores.
Teoricamente, é possível listar todas as máquinas Turing de um determinado comprimento ou todos os programas Python de um determinado comprimento e encontrar o menor que execute essa tarefa, mas a lista cresce exponencialmente com o aumento do comprimento.
No entanto, é possível calcular a duração de programas específicos se estivermos lidando com algumas das dificuldades mencionadas acima. Poderíamos fazer do Landau um jogo para dois, vendo quem pode oferecer uma solução mais simples em um período fixo de tempo.
Voltar para Landau
Se permitirmos seno e grau em nosso conjunto de operadores, então B.S. Gorobets é uma solução universal. Para n ≥ 6, n! um múltiplo de 360, e assim
sin (n!) ° = 0.
E se n for menor que 6, sua representação de dois dígitos começa em zero, para que possamos multiplicar os números para obter zero.
Se proibimos funções transcendentais, bloqueamos o truque de Gorobets e temos funções cujo comprimento podemos medir objetivamente em uma linguagem de programação.