Proceedings

Towards a Mathematical Theory of Program Synthesis

Download BibTeX Cite

Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .

© 1979 International Joint Conferences on Artificial Intelligence

Abstract

This paper attempts to set a theoretical foundation for Program Synthesis. A programming language Prog is introduced together with its interpretation in the semantic domain D. A formal system QFT, which is an extension of the Heyting arithmetic, is then introduced in order to express specifications formally. Roughly stated, the main result is: Given a QFT-proof of the specification ~x~zA[x,z], it is possible to construct a program p such that A[x,p[x]] is true in D for any input x. Moreover, a formal proof of ~xA[x,p[x]] can also be obtained. Since any program p in Prog always terminates, the above result establishes the total correctness of the synthesized program at the same time. Finally, it is shown that any program p in Prog can be faithfully simulated by means of LISP.

  1. Burstall, R.M. and Goguen, J.A. 1977] Putting thories together to make specifications, Proc. IJCAI-77. MIT, Cambridge, Mass., 1045-1058.
  2. G~del, K. 1958] Uber eine bisher noah nicht benUtzte erwriterung des finiten Standpunktes, Dialectica, 12, 280-287.
  3. Goto, S. 1978] Program synthesis through ~del's interpretation, Proc. International Conference on Mathematical Studies of Information Processing, 287-306, Kyoto.
  4. Howard, W.A. 1970] Assignment of ordinals to terms of primitive recursive funotionals of finite type, Intuitionism and Proof Theory, 443-458, North-Holland.
  5. Kreisel, G. 1977] Some uses of proof theory for finding computer programs, Colloque International des Logique, 123-134, Paris.
  6. Shoenfield, J.R. 1967] Mathematical Logic, Addison Wesley.
  7. ShUtte, K. 1977] Proof Theory, Springer.
  8. Takahashi, M. 1977] A foundation of finite math- ematics, Publ. RIMS, Kyoto Univ., 12, 577-708 .
  9. Takasu, S. 1978] Proofs and programs, Proc. 3rd IBM symposium on Mathematical Foundations of Com- puter Science, IBM Japan.
  10. Takeuti, G. 1975] Proof Theory, North-Holland.
  11. Troelstra, A.S. 1972] Review of [Yasugi 1963], J. of Symbolic Logic, 37, 404.
  12. Troelstra, A.S. 1973]--Mathematical Investiga- tions of intuitionistic arithmetic and analysis, Lecture Notes in Mathematics 344, Springer.
  13. Yasugi, M. 1963] Intuitionistic analysis and ~del's interpretation, J. Math. Soc. Japan, 15, 101-112.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards