Existe alguma esperança de usar um computador para adivinhar fórmulas combinatórias para uma sequência de valores inteiros, dados alguns termos iniciais?

Às vezes, em combinatória, você está computando a contagem de algo que depende de um parâmetro numérico natural . Manualmente ou usando um computador, é possível calcular alguns termos iniciais na sequência$a_n$$n$$(a_n)_n$. Agora, você pode inserir esses termos iniciais na Enciclopédia on-line de seqüências inteiras e, se tiver sorte, poderá obter uma correspondência com uma fórmula e informações que o ajudarão a provar que sua sequência satisfaz essa fórmula. Mas e se sua sequência exata não for documentada, mas estiver diretamente relacionada a uma sequência conhecida? Como se sua sequência fosse dupla ou o quadrado de outra sequência conhecida? Ou se sua sequência pode ser expressa diretamente ou como um somatório envolvendo termos hipergeométricos? Se um computador puder propor fórmulas para uma sequência com alguns termos iniciais, isso poderá ajudar imensamente o matemático, porque quando eles finalmente olharem para a fórmula correta, poderá ficar claro para eles por que a fórmula é verdadeira com base na estrutura do problema e na Fórmula. Houve algum progresso em permitir que os computadores "adivinhem"

Uma solução exata para esse problema é obviamente impossível (por exemplo, é a sequência de números inteiros ímpares ou de números primos?), Mas existem maneiras de obter respostas quando a sequência não está em oeis, mas está "relacionada" a algumas sequência no banco de dados.$3,5,7$

Uma maneira de fazer isso é usar o super-candidato . Basicamente, você envia a sequência que chegou para [email protected] e, em seguida, o servidor tenta alguns algoritmos para encontrar um relacionamento entre sua sequência e as que estão em oeis.

Portanto, um bom começo é verificar que tipo de testes / algoritmos são usados ​​pelo super-candidato (iirc, há uma descrição sobre isso em algum lugar do site)

isso é realmente implementado em uma função mathematica relativamente nova chamada FindSequenceFunction e é bem-sucedida em casos básicos. pode ser considerado um modelo e quase o estado da arte na área.

no entanto, o problema geral é muito transversal e aborda muitos campos / técnicas, como aprendizado de máquina , prova automatizada de teoremas , indução matemática e complexidade de Kolmogorov (onde a solução de problemas muito semelhante se baseia em "encontrar a menor MT que gera uma sequência") e até mesmo mergulhar na filosofia como "o problema da indução" . todos esses campos têm pesquisas ativas na área. ele também aparece no ajuste de curvas e estatísticas / big data, mas as seqüências são mais aproximadas, embora geralmente se apliquem os mesmos princípios abstratos.

o problema geral não é decidível, mas também não é exatamente correto chamá-lo de "indecidível". está sempre sujeito a "falsos positivos" (sequências que correspondem ao número limitado de entradas, mas não mais) e "falsos negativos" (sequências que possuem fórmulas, mas que não são detectáveis ​​pelo "the" ou por qualquer algoritmo). é seguro dizer que as pesquisas nessa área continuarão por décadas no futuro e, na verdade, provavelmente enquanto houver pesquisas matemáticas realizadas por seres humanos.