Axiomatic Synthesis of Computer Programs and Computability Theorems

Details Axiomatic Synthesis of Computer Programs and Computability Theorems Axiomatic Synthesis of Computer Programs and Computability Theorems

2000-03-22

arxiv.org/abs/cs/0003071v1

Computer Science

Logic in Computer Science

for submission to Journal of the ACM

Scientific paper

We introduce a set of eight universal Rules of Inference by which computer programs with known properties (axioms) are transformed into new programs with known properties (theorems). Axioms are presented to formalize a segment of Number Theory, DataBase retrieval and Computability Theory. The resulting Program Calculus is used to generate programs to (1) Determine if one number is a factor of another. (2) List all employees who earn more than their manager. (3) List the set of programs that halt no on themselves, thus proving that it is recursively enumerable. The well-known fact that the set of programs that do not halt yes on themselves is not recursively enumerable is formalized as a program requirement that has no solution, an Incompleteness Axiom. Thus, any axioms (programs) which could be used to generate this program are themselves unattainable. Such proofs are presented to formally generate several additional theorems, including (4) The halting problem is unsolvable. Open problems and future research is discussed, including the use of temporary sort files, programs that calculate statistics (such as counts and sums), the synthesis of programs to solve other well-known problems from Number Theory, Logic, DataBase retrieval and Computability Theory, application to Programming Language Semantics, and the formalization of incompleteness results from Logic and the semantic paradoxes.

Affiliated with

Also associated with

No associations

Rating

Axiomatic Synthesis of Computer Programs and Computability Theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Axiomatic Synthesis of Computer Programs and Computability Theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Axiomatic Synthesis of Computer Programs and Computability Theorems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475197