On completeness of program synthesis systems

From MaRDI portal





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].











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)