Driven by the question, 'What is the computational content of a (formal) proof?', this book studies fundamental interactions between proof theory and computability. It provides a unique self-contained text for advanced students and researchers in mathematical logic and computer science. Part I covers basic proof theory, computability and Gödel's theorems. Part II studies and classifies provable recursion in classical systems, from fragments of Peano arithmetic up to Π11-CA0. Ordinal analysis and the (Schwichtenberg-Wainer) subrecursive hierarchies play a central role and (...) are used in proving the 'modified finite Ramsey' and 'extended Kruskal' independence results for PA and Π11-CA0. Part III develops the theoretical underpinnings of the first author's proof assistant MINLOG. Three chapters cover higher-type computability via information systems, a constructive theory TCF of computable functionals, realizability, Dialectica interpretation, computationally significant quantifiers and connectives and polytime complexity in a two-sorted, higher-type arithmetic with linear logic. (shrink)

Let A be a formula without implications, and Γ consist of formulas containing disjunction and falsity only negatively and implication only positively. Orevkov and Nadathur proved that classical derivability of A from Γ implies intuitionistic derivability, by a transformation of derivations in sequent calculi. We give a new proof of this result , where the input data are natural deduction proofs in long normal form involving stability axioms for relations; the proof gives a quadratic algorithm to remove the stability axioms. (...) This can be of interest for computational uses of classical proofs. (shrink)

Consider the problem which set V of propositional variables suffices for whenever, where, and ⊢c and ⊢i denote derivability in classical and intuitionistic implicational logic, respectively. We give a direct proof that stability for the final propositional variable of the (implicational) formula A is sufficient; as a corollary one obtains Glivenko's theorem. Conversely, using Glivenko's theorem one can give an alternative proof of our result. As an alternative to stability we then consider the Peirce formula. It is an easy consequence (...) of the result above that adding a single instance of the Peirce formula suffices to move from classical to intuitionistic derivability. Finally we consider the question whether one could do the same for minimal logic. Given a classical derivation of a propositional formula not involving ⊥, which instances of the Peirce formula suffice as additional premises to ensure derivability in minimal logic? We define a set of such Peirce formulas, and show that in general an unbounded number of them is necessary. (shrink)

From a classical proof that the gcd of natural numbers a1 and a2 is a linear combination of the two, we extract by Gödel's Dialectica interpretation an algorithm computing the coefficients. The proof uses the minimum principle. We show generally how well-founded recursion can be used to Dialectica interpret well-founded induction, which is needed in the proof of the minimum principle. In the special case of the example above it turns out that we obtain a reasonable extracted term, representing an (...) algorithm close to Euclid's. (shrink)

Buchholz presented a method to build notation systems for infinite sequent-style derivations, analogous to well-known systems of notation for ordinals. The essential feature is that from a notation one can read off by a primitive recursive function its n th predecessor and, e.g. the last rule applied. Here we extend the method to the more general setting of infinite terms, in order to make it applicable in other proof-theoretic contexts as well as in recursion theory. As examples, we use the (...) method to 1. give a new proof of a well-known trade-off theorem , which says that detours through higher types can be eliminated by the use of transfinite recursion along higher ordinals, and 2. construct a continuous normalization operator with an explicit modulus of continuity. (shrink)

The paper presents a refined method of extracting reasonable and sometimes unexpected programs from classical proofs of formulas of the form ∀x∃yB . We also generalize previously known results, since B no longer needs to be quantifier-free, but only has to belong to a strictly larger class of so-called “goal formulas”. Furthermore we allow unproven lemmas D in the proof of ∀x∃yB , where D is a so-called “definite” formula.

Several properties of monotone functionals (MF) and monotone majorizable functionals (MMF) used in the earlier work by the author and van de Pol are proved. It turns out that the terms of the simply typed lambda-calculus define MF, but adding primitive recursion, and even monotonic primitive recursion changes the situation: already Z.Z(1 — sg) is not MMF. It is proved that extensionality is not Dialectica-realizable by MMF, and a simple example of a MF which is not hereditarily majorizable is given.

Proceedings of the NATO Advanced Study Institute on Proof and Computation, held in Marktoberdorf, Germany, July 20 - August 1, 1993.

This is a tutorial for the Minlog Proof Assistant, version 5.0.

"First published by Oxford University Press, 1916."--Title page verso.

This is the first complete, one-volume English translation of the ancient Chinese text Xunzi, one of the most extensive, sophisticated, and elegant works in the tradition of Confucian thought. Through essays, poetry, dialogues, and anecdotes, the Xunzi articulates a Confucian perspective on ethics, politics, warfare, language, psychology, human nature, ritual, and music, among other topics. Aimed at general readers and students of Chinese thought, Eric Hutton’s translation makes the full text of this important work more accessible in English than ever (...) before. Named for its purported author, the Xunzi has long been neglected compared to works such as the Analects of Confucius and the Mencius. Yet interest in the Xunzi has grown in recent decades, and the text presents a much more systematic vision of the Confucian ideal than the fragmented sayings of Confucius and Mencius. In one famous, explicit contrast to them, the Xunzi argues that human nature is bad. However, it also allows that people can become good through rituals and institutions established by earlier sages. Indeed, the main purpose of the Xunzi is to urge people to become as good as possible, both for their own sakes and for the sake of peace and order in the world. In this edition, key terms are consistently translated to aid understanding and line numbers are provided for easy reference. Other features include a concise introduction, a timeline of early Chinese history, a list of important names and terms, cross-references, brief explanatory notes, a bibliography, and an index. (shrink)

This incisive book deals with the use of the criminal law to enforce morality, in particular sexual morality, a subject of particular interest and importance since the publication of the Wolfenden Report in 1957. Professor Hart first considers John Stuart Mill's famous declaration: "The only purpose for which power can be rightfully exercised over any member of a civilized community is to prevent harm to others." During the last hundred years this doctrine has twice been sharply challenged by two great (...) lawyers: Sir James Fitzjames Stephen, the great Victorian judge and historian of the common law, and Lord Devlin, who both argue that the use of the criminal law to enforce morality is justified. The author examines their arguments in some detail, and sets out to demonstrate that they fail to recognize distinction of vital importance for legal and political theory, and that they espouse a conception of the function of legal punishment that few would now share. (shrink)