Logique en calcul
La logique en calcul applique les outils de la logique mathématique pour décrire, spécifier et raisonner sur les systèmes computationnels, et pour caractériser les classes de complexité par les ressources logiques nécessaires à la définition de leurs problèmes.
Definition
La logique en calcul est l'étude des systèmes logiques formels en tant que langages pour spécifier et vérifier le comportement computationnel et en tant qu'étalon de mesure de la complexité computationnelle, traitant le calcul et la définissabilité logique comme deux facettes des mêmes phénomènes.
Scope
Ce domaine couvre les logiques temporelles et modales pour la spécification du comportement des programmes et des systèmes réactifs, la complexité descriptive qui assimile les classes de complexité à la définissabilité logique, et la lecture computationnelle des théorèmes d'incomplétude de Gödel et leur relation à l'indécidabilité, s'appuyant sur la longue interaction entre la logique et l'informatique.
Sub-topics
Core questions
- Comment les formules logiques peuvent-elles spécifier le comportement correct des programmes et des systèmes ?
- Les classes de complexité peuvent-elles être caractérisées uniquement par l'expressivité logique ?
- Quel est le contenu computationnel des théorèmes d'incomplétude de Gödel ?
- Comment la logique et le calcul éclairent-ils mutuellement leurs limites ?
Key theories
- Complexité descriptive
- Les principales classes de complexité coïncident avec les classes de problèmes définissables dans des logiques particulières, de sorte que les ressources de calcul peuvent être mesurées par la puissance expressive logique plutôt que par le temps ou l'espace machine.
- Logiques pour le comportement des programmes
- Les logiques temporelles, modales et dynamiques fournissent des langages précis pour spécifier des propriétés telles que la sûreté (safety) et la vivacité (liveness), formant la base de la vérification formelle du matériel et des logiciels.
Clinical relevance
La spécification logique du comportement des systèmes sous-tend la vérification formelle et la vérification de modèles (model checking) utilisées pour certifier les matériels et logiciels critiques pour la sécurité, tandis que la complexité descriptive offre une perspective indépendante de la machine sur la traitabilité qui éclaire les langages de requête de bases de données et les fondements de la théorie de la complexité.
History
Le lien entre la logique et le calcul s'étend de Gödel et Turing dans les années 1930 à l'essor de l'informatique. Le théorème de Fagin de 1974 a lancé la complexité descriptive, Pnueli a introduit la logique temporelle pour les programmes en 1977, et la vérification de modèles (model checking) s'est développée dans les années 1980 pour devenir une technologie de vérification majeure, approfondissant les fondements logiques du domaine.
Key figures
- Kurt Gödel
- Amir Pnueli
- Neil Immerman
- Ronald Fagin
Related topics
Seminal works
- immerman1999
- harel2000
Frequently asked questions
- Comment la logique est-elle utilisée en informatique au-delà des mathématiques pures ?
- La logique fournit des langages pour énoncer précisément ce qu'un système doit faire et des méthodes pour prouver qu'il le fait. Les logiques temporelles spécifient le comportement continu, les systèmes de types et les logiques de programmes certifient le code, et la complexité descriptive reformule l'efficacité en termes de définissabilité, faisant de la logique un outil d'ingénierie pratique ainsi qu'un fondement.
- Que révèle la complexité descriptive ?
- Elle montre que les classes de complexité peuvent être définies sans référence aux machines ou aux bornes de temps, uniquement par la logique qui peut exprimer leurs problèmes. Par exemple, les problèmes résolubles en temps polynomial sur des structures ordonnées sont exactement ceux définissables dans une certaine extension de la logique du premier ordre, reliant le calcul à l'expressivité logique.