Axiomatic Synthesis of Computer Programs and Computability Theorems

This article presents a survey of computability logic: its philosophy and motivations, main concepts and most significant results obtained so far. A continuously updated online version of this article is maintained at http://www.csc.villanova.edu/~japaridz/CL/ .

Recent advances in computing have changed not only the nature of mathematical computation, but mathematical proof and inquiry itself. While artificial intelligence and formalized mathematics have been the major topics of this conversation, this paper explores another class of tools for advancing mathematics research: databases of mathematical objects that enable semantic search. In addition to defining and exploring examples of these tools, we illustrate a particular line of ...

We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The local-rule-set transformation gives polynomial-time evaluation strategies for a large variety of rule sets that cannot be given terminating evaluation strategies by any other known automatic technique. This paper discusses three new results. First, it is shown that every polynomial-time p...

This research is about operational- and complexity-oriented aspects of classical foundations of computability theory. The approach is to re-examine some classical theorems and constructions, but with new criteria for success that are natural from a programming language perspective. Three cornerstones of computability theory are the S-m-ntheorem; Turing's "universal machine"; and Kleene's second recursion theorem. In today's programming language parlance these are respective...

Mechanical reasoning is a key area of research that lies at the crossroads of mathematical logic and artificial intelligence. The main aim to develop mechanical reasoning systems (also known as theorem provers) was to enable mathematicians to prove theorems by computer programs. However, these tools evolved with time and now play vital role in the modeling and reasoning about complex and large-scale systems, especially safety-critical systems. Technically, mathematical formal...

A re-construction of the fundamentals of programming as a small mathematical theory (PRISM) based on elementary set theory. Highlights: $\bullet$ Zero axioms. No properties are assumed, all are proved (from standard set theory). $\bullet$ A single concept covers specifications and programs. $\bullet$ Its definition only involves one relation and one set. $\bullet$ Everything proceeds from three operations: choice, composition and restriction. $\bullet$ These techniq...

It is well known that many theorems in recursion theory can be "relativized". This means that they remain true if partial recursive functions are replaced by functions that are partial recursive relative to some fixed oracle set. Uspensky formulates three "axioms" called "axiom of computation records", "axiom of programs'" and "arithmeticity axiom". Then, using these axioms (more precisely, two first ones) he proves basic results of the recursion theory. These two axioms are ...

We argue that Godel's completeness theorem is equivalent to completability of consistent theories, and Godel's incompleteness theorem is equivalent to the fact that this completion is not constructive, in the sense that there are some consistent and recursively enumerable theories which cannot be extended to any complete and consistent and recursively enumerable theory. Though any consistent and decidable theory can be extended to a complete and consistent and decidable theor...

We discuss views about whether the universe can be rationally comprehended, starting with Plato, then Leibniz, and then the views of some distinguished scientists of the previous century. Based on this, we defend the thesis that comprehension is compression, i.e., explaining many facts using few theoretical assumptions, and that a theory may be viewed as a computer program for calculating observations. This provides motivation for defining the complexity of something to be th...

This is a set of 288 questions written for a Moore-style course in Mathematical Logic. I have used these (or some variation) four times in a beginning graduate course. Topics covered are: propositional logic axioms of ZFC wellorderings and equivalents of AC ordinal and cardinal arithmetic first order logic, and the compactness theorem Lowenheim-Skolem theorems Turing machines, Church's Thesis completeness theorem and first incompleteness theorem undecidable ...