Uma ferramenta para verificar as estimativas, ii: um assistente de prova flexível

Em um Postagem recenteEu falei sobre um Ferramenta de prova de conceito Para verificar as estimativas automaticamente. Desde esse publish, revisei a ferramenta duas vezes: primeiro transformá -lo em um assistente de prova rudimentar que também poderia lidar com alguma lógica proposicional; e o segundo em um assistente de prova muito mais flexível (deliberadamente projetado para imitar o Assistente de Prova Lean em vários aspectos -chave) que também é alimentado pelo extenso pacote Python Simpy para álgebra simbólica, seguindo o suggestions de comentaristas anteriores. Acho que isso agora é uma estrutura estável com a qual se pode estender a ferramenta muito mais longe; Meu objetivo inicial period apenas automatizar (ou semi-automatiza) a prova de estimativas assintóticas envolvendo funções escalares, mas, em princípio, alguém poderia continuar adicionando táticas, novos tipos de sympy e lemas à ferramenta para lidar com uma gama muito ampla de outras tarefas matemáticas também.

A versão atual do assistente de prova pode ser encontrada aqui. (Como na minha codificação anterior, acabei confiando muito on giant language mannequin help to grasp a number of the finer factors of Python and sympy, with the autocomplete function of Github Copilot being significantly helpful.) Whereas the software can assist absolutely automated proofs, I’ve determined to focus extra for now on semi-automated interactive proofs, the place the human person provides high-level “techniques” that the proof assistant then performs the required calculations for, till the proof is accomplished.

É mais fácil explicar como o assistente de prova trabalha com exemplos. No momento, implementei o assistente para trabalhar dentro do modo interativo de pythonem que se entra em Python comanda um de cada vez. (Os leitores da minha geração podem estar familiarizados com os jogos de aventura de texto, que têm uma interface amplamente semelhante.) Eu estaria interessado em desenvolver em algum momento uma interface gráfica do usuário para a ferramenta, mas para fins de protótipo, a versão interativa do Python é suficiente. (Também é possível executar o assistente de prova em um script python, é claro.)

Depois de baixar os arquivos relevantes, pode -se iniciar o assistente de prova dentro do Python digitando from primary import * e depois carregar um dos exercícios pré-fabricados. Aqui está um desses exercícios:

>>> from primary import *
>>> p = linarith_exercise()
Beginning proof.  Present proof state:
x: pos_real
y: pos_real
z: pos_real
h1: x < 2*y
h2: y < 3*z + 1
|- x < 7*z + 2

Esta é a formalização do assistente de prova do seguinte problema: se são reais positivos de tal forma que e show isso .

A maneira como o assistente de prova trabalha é que alguém instrui o assistente a usar várias “táticas” para simplificar o problema até que ele seja resolvido. Nesse caso, o problema pode ser resolvido pela aritmética linear, como formalize dby o Linarith() tática:

>>> p.use(Linarith())
Objective solved by linear arithmetic!
Proof full!

Se, em vez disso, se quisesse um pouco mais de detalhes sobre como a aritmética linear funcionava, poderia ter executado essa tática em vez de verbose bandeira:

>>> p.use(Linarith(verbose=true))
Checking feasibility of the next inequalities:
1*z > 0
1*x + -7*z >= 2
1*y + -3*z < 1
1*y > 0
1*x > 0
1*x + -2*y < 0
Infeasible by summing the next:
1*z > 0 multiplied by 1/4
1*x + -7*z >= 2 multiplied by 1/4
1*y + -3*z < 1 multiplied by -1/2
1*x + -2*y < 0 multiplied by -1/4
Objective solved by linear arithmetic!
Proof full!

Às vezes, a prova envolve a divisão de casos e, em seguida, a prova closing tem a estrutura de uma árvore. Aqui está um exemplo, onde a tarefa é mostrar que as hipóteses e implicar :

>>> from primary import *
>>> p = split_exercise()
Beginning proof.  Present proof state:
x: actual
y: actual
h1: (x > -1) & (x < 1)
h2: (y > -2) & (y < 2)
|- (x + y > -3) & (x + y < 3)
>>> p.use(SplitHyp("h1"))
Decomposing h1: (x > -1) & (x < 1) into elements x > -1, x < 1.
1 purpose remaining.
>>> p.use(SplitHyp("h2"))
Decomposing h2: (y > -2) & (y < 2) into elements y > -2, y < 2.
1 purpose remaining.
>>> p.use(SplitGoal())
Cut up into conjunctions: x + y > -3, x + y < 3
2 targets remaining.
>>> p.use(Linarith())
Objective solved by linear arithmetic!
1 purpose remaining.
>>> p.use(Linarith())
Objective solved by linear arithmetic!
Proof full!
>>> print(p.proof())
instance (x: actual) (y: actual) (h1: (x > -1) & (x < 1)) (h2: (y > -2) & (y < 2)): (x + y > -3) & (x + y < 3) := by
  split_hyp h1
  split_hyp h2
  split_goal
  . linarith
  linarith

Aqui no closing, demos uma descrição de “pseudo-lean” da prova em termos das três táticas usadas: uma tática circumstances h1 para case dividido na hipótese h1seguido por duas aplicações do simp_all Tática a ser simplificada em cada um dos dois casos.

A ferramenta suporta estimativa assintótica. Encontrei uma maneira de implementar o Ordem de magnitude formalismo do publish anterior dentro de simpy. Acontece que a simpy, em certo sentido, já implementa nativamente análise fora do padrão: suas variáveis ​​simbólicas têm um is_number A bandeira que basicamente corresponde ao conceito de um número “padrão” em análise fora do padrão. Por exemplo, o sympy versão S(3) do número 3 tem S(3).is_number == True e o mesmo é padrão, enquanto uma variável inteira n = Image("n", integer=true) tem n.is_number == False E o mesmo acontece com o não -padrão. Dentro de sympyPude construir ordens de magnitude Theta(X) de várias expressões (positivas) Xcom a propriedade que Theta(n)=Theta(1) se n é um número padrão e use esse conceito para definir estimativas assintóticas, como (implementado como lesssim(X,Y)). Pode -se então aplicar uma forma logarítmica de aritmética linear para verificar automaticamente algumas estimativas assintóticas. Aqui está um exemplo simples, no qual se recebe um número inteiro positivo e reais positivos tais que e e a tarefa é concluir que :

>>> p = loglinarith_exercise()
Beginning proof.  Present proof state:
N: pos_int
x: pos_real
y: pos_real
h1: x <= 2*N**2
h2: y < 3*N
|- Theta(x)*Theta(y) <= Theta(N)**4
>>> p.use(LogLinarith(verbose=True))
Checking feasibility of the next inequalities:
Theta(N)**1 >= Theta(1)
Theta(x)**1 * Theta(N)**-2 <= Theta(1)
Theta(y)**1 * Theta(N)**-1 <= Theta(1)
Theta(x)**1 * Theta(y)**1 * Theta(N)**-4 > Theta(1)
Infeasible by multiplying the next:
Theta(N)**1 >= Theta(1) raised to energy 1
Theta(x)**1 * Theta(N)**-2 <= Theta(1) raised to energy -1
Theta(y)**1 * Theta(N)**-1 <= Theta(1) raised to energy -1
Theta(x)**1 * Theta(y)**1 * Theta(N)**-4 > Theta(1) raised to energy 1
Proof full!

O solucionador de programação linear logarítmica também pode lidar com termos de ordem inferior, por um método de ramificação de força bastante bruta:

>>> p = loglinarith_hard_exercise()
Beginning proof.  Present proof state:
N: pos_int
x: pos_real
y: pos_real
h1: x <= 2*N**2 + 1
h2: y < 3*N + 4
|- Theta(x)*Theta(y) <= Theta(N)**3
>>> p.use(LogLinarith())
Objective solved by log-linear arithmetic!
Proof full!

Planejo começar a desenvolver ferramentas para estimar as normas de espaço de função das funções simbólicas, por exemplo, criando táticas para implantar lemas como a desigualdade do titular e a desigualdade de incorporação de Sobolev. Parece o sympy A estrutura é flexível o suficiente para permitir a criação de outras courses de objetos para esses tipos de objetos. (Agora, eu só tenho Um lema de prova de conceito Para ilustrar a estrutura, o lema médio-geométrico aritmético.)

Estou satisfeito o suficiente com a estrutura básica desse assistente de prova de que eu estaria aberto a sugestões ou contribuições adicionais de novos recursos, por exemplo, introduzindo novos tipos de dados, lemas e táticas, ou contribuindo com problemas de exemplo que devem ser facilmente solucionáveis ​​por tal assistente, mas atualmente estão além de sua capacidade, por exemplo, devido à falta de táticas apropriadas e lenmas.