  Computability logic (CL) (see http://www.cis.upenn.edu/~giorgi/cl.html) is a
recently launched program for redeveloping logic as a formal theory of
computability, as opposed to the formal theory of truth that logic has more
traditionally been. Formulas in it represent computational problems, "truth"
means existence of an algorithmic solution, and proofs encode such solutions.
Within the line of research devoted to finding axiomatizations for ever more
expressive fragments of CL, the present paper introduces a new deductive system
CL12 and proves its soundness and completeness with respect to the semantics of
CL. Conservatively extending classical predicate calculus and offering
considerable additional expressive and deductive power, CL12 presents a
reasonable, computationally meaningful, constructive alternative to classical
logic as a basis for applied theories. To obtain a model example of such
theories, this paper rebuilds the traditional, classical-logic-based Peano
arithmetic into a computability-logic-based counterpart. Among the purposes of
the present contribution is to provide a starting point for what, as the author
wishes to hope, might become a new line of research with a potential of
interesting findings -- an exploration of the presumably quite unusual
metatheory of CL-based arithmetic and other CL-based applied systems.
