On completeness of program synthesis systems
decidable predicatesexpressibility completeness in logical systemsprogram synthesisrecursive functions
Recursive functions and relations, subrecursive hierarchies (03D20) Abstract and axiomatic computability and recursion theory (03D75) Constructive and recursive analysis (03F60) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
The goal of the paper is to investigate cases when there is a logical system allowing to extract all total recursive functions (all partial recursive functions, all decidable predicates) from proofs in this logical system. Another question is whether such systems do exist among some known systems. The author obtains the following interesting results (\(\bar x\) denotes the vector notation, and \(\text{In}(\bar x)\) is a Harrop formula): (1) It is impossible to extract programs for all total recursive functions from the proofs of specifications of the form \(\forall \bar x \exists y\text{ Out}(x,y)\); (2) It is impossible to extract algorithms deciding all decidable predicates from the proofs of specifications of the form \(\forall \bar x(P(\bar x)\lor\neg P(\bar x))\); In the system \(\text{HA}+\text{MP}\) (Heyting Arithmetic \(+\) all instances of Markov's Principle) (3) it is possible to extract all partial recursive functions from the specifications of the form \(\forall \bar x(\text{In}(\bar x)\supset \exists y \text{Out}(\bar x,y))\); (4) It is possible to extract algorithms deciding all decidable predicates from the specifications of the form \(\forall \bar x(\text{In}(\bar x)\supset (P(\bar x)\lor\neg P(\bar x)))\). For the entire collection see [Zbl 0772.68004].
- Proofs and programs: A naïve approach to program extraction
- scientific article; zbMATH DE number 4134025
- Extraction and verification of programs by analysis of formal proofs
- Automated synthesis of recursive programs from a logical specification
- On automating the extraction of programs from proofs using product types
- scientific article; zbMATH DE number 4174908 (Why is no real title available?)
- scientific article; zbMATH DE number 3932374 (Why is no real title available?)
- Soundness and completeness of a synthesis algorithm based on example computations
- scientific article; zbMATH DE number 4055607 (Why is no real title available?)
- On automating the extraction of programs from proofs using product types
- Completeness of combinations of constructor systems
- Completeness of Conversion between Reactive Programs for Ultrametric Models
- Completeness, minimal logic and programs extraction
- Completeness of synthesis under realizability assumptions using superposition
This page was built for publication: On completeness of program synthesis systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202961)