Pourquoi certains moteurs d'inférence ont-ils besoin d'une assistance humaine alors que d'autres n'en ont pas?

16

Je suis d' apprentissage automatisé théorème prouvons / solveurs SMT / assistants de preuve par moi - même et après une série de questions au sujet du processus, en commençant ici .

Pourquoi les prouveurs de théorèmes automatisés, c'est-à-dire ACL2 et les solveurs SMT, n'ont-ils pas besoin de l'assistance humaine alors que les assistants de preuve, c'est-à-dire Isabelle et Coq , en ont besoin ?

Trouvez la prochaine question de la série ici .

logic proof-assistants automated-theorem-proving smt-solvers Guy Coder
la source

Réponses:

14

La validité des formules d'ordre supérieur n'est généralement pas décidable et les espaces de recherche sont énormes , donc tout ce que vous pouvez espérer faire est d' essayer de trouver une preuve - en supposant qu'elle existe - en énumérant intelligemment l'espace de preuve (pensez à sledgehammer , bien nommé) mais c'est rude. Les humains peuvent jouer l'oracle, fournissant les lemmes clés pour guider la preuve.

Les prouveurs automatisés, en revanche, ne traitent généralement que des (sous-ensembles de) logiques décidables, par exemple la logique propositionnelle ou les sous-classes de logique de premier ordre, de sorte qu'ils peuvent fonctionner longtemps, mais vous savez qu'ils finiront par réussir.

Notez qu'il existe des approches pour permettre aux assistants de preuve de trouver ces lemmes importants, par exemple IsaPlanner . L'outil devine les lemmes (inductifs) par énumération et tests aléatoires, puis essaie de les prouver. En itérant le processus, de nombreux lemmes de définitions de types de données, par exemple, peuvent être trouvés automatiquement.

Petit ABC

  • validité - une formule est valide, elle contient tout ce que vous affectez aux variables libres.
  • variables libres - les variables qui ne sont pas liées par des quantificateurs tels que et ∃∀∃
  • décidabilité - une propriété (booléenne) est (Turing) décidable s'il existe un algorithme qui répond «oui» ou «non» (correctement) après un laps de temps fini.
  • logique propositionnelle - également logique d'ordre zéro ; aucune quantification autorisée.
  • ∀X.P(X)∀F.F(4)>0
  • logique d'ordre supérieur - vous pouvez quantifier (et "construire") des objets arbitrairement complexes, par exemple des fonctions d'ordre supérieur (fonctions qui prennent des fonctions).
Raphael
la source
@GuyCoder: Je ne suis pas sûr que ce soit faisable, cependant. Nous ne pouvons pas écrire chaque réponse de telle sorte qu'elle soit digestible sans connaissance préalable. Les ATP sont des trucs avancés; Je ne recommanderais à personne de les apprendre sans une solide formation en logique. Écrire des réponses comme vous semblez les vouloir ne peut que créer une illusion de compréhension mais n'aide pas vraiment, à mon humble avis. Donc, toutes les personnes intéressées par votre série devraient d'abord faire quelques logiques, que nous pouvons également aider - dans d'autres questions.
Raphael
7

Je dirais qu'il faut reconsidérer la distinction classique entre "démonstration automatique de théorèmes" (ATP) et "démonstration interactive de théorèmes" (ITP). Si vous prenez aujourd'hui un système ITP bien connu comme Isabelle / HOL (Isabelle2013 de février 2013), il intègre pas mal d'outils complémentaires du portefeuille ATP:

  • Outils de preuve automatisés génériques embarqués: outils Isabelle à l'ancienne comme fastet blast(par L. Paulson) et nouveaux prouveurs automatisés comme metis(par J. Hurd).

  • ATP externes pour la logique du premier ordre qui sont invoqués via Sledgehammer: E prover, SPASS, Vampire. La preuve qui est trouvée est analysée pour déterminer quels lemmes y ont contribué, réduisant les 10000 à 10 secondes et alimentant le résultat metis.

  • SMT externes avec reconstruction de preuve partielle, notamment pour Z3 (par S. Boehme).

  • Outils pour trouver des contre-exemples de déclarations non prouvées: Nitpick / Kodkodi (J. Blanchette) et Quickcheck (L. Bulwahn).

Est-ce que tout cela automatisé fait d'Isabelle un prouveur de théorème automatisé?

En fin de compte, je pense que la distinction entre "ATP" et "ITP" n'est qu'une sorte de "label" qui indique comment vous voulez positionner ou "vendre" votre système: les ATP prétendent être des "outils à bouton-poussoir", mais dans pratique, vous devrez interagir (indirectement), en fournissant des paramètres ou des conseils, ou en reformulant votre problème. Cela pourrait en fait être assez difficile, en raison des longs délais d'exécution qui sont monnaie courante dans la communauté ATP.

En revanche, un système ITP est conçu pour les personnes qui attendent sur place, avec un accès à moitié décent aux états de preuve internes, pour voir ce qui manque pour terminer une preuve. Un système ITP qui englobe les outils ATP à la manière d'Isabelle pourrait s'avérer plus attrayant pour plus d'utilisateurs et plus d'applications que ITP ou ATP seuls.

Makarius
la source
Cela fait un moment, mais si je me souviens bien, fastni blastles prouveurs; ce sont essentiellement des heuristiques utilisant certaines règles qui peuvent trouver une preuve. (Bien sûr, ce sont des prouveurs sur un sous-ensemble de formules convenablement petit, ce qui est vrai pour toute méthode d'énumération de preuves.)
Raphael
2
Lorsque vous dites "prouveur", voulez-vous dire en fait "procédure de décision" pour une certaine langue fixe? La plupart des "prouveurs" ATP sont des procédures de semi-décision, la façon dont vous avez caractérisé fastet blast. Notez que blastL. Paulson a présenté comme "Un générateur de tableau générique et son intégration avec Isabelle" à un atelier CADE - l'article est apparu plus tard dans J. UCS 1999. Isabelle a plus de "provers" et ce sens, par exemple les métis, mais également des procédures de décision pour certaines langues spéciales (sous-ensembles d'arithmétique).
Makarius