This lively introduction to mathematical logic, easily accessible to non-mathematicians, offers an historical survey, coverage of predicate calculus, model theory, Godel’s theorems, computability and recursivefunctions, consistency and independence in axiomatic set theory, and much more. Suggestions for Further Reading. Diagrams.
The paper presents a brief survey of recent work by Metakides, Nerode and others in the area of effective algebra and makes some comments on the relation between formal presentations, characterizations, etc. of sets and of algebraic structures and their practical presentations.
In this paper we 1. provide a natural deduction system for full first-order linear logic, 2. introduce Curry-Howard-style terms for this version of linear logic, 3. extend the notion of substitution of Curry-Howard terms for term variables, 4. define the reduction rules for the Curry-Howard terms and 5. outline a proof of the strong normalization for the full system of linear logic using a development of Girard's candidates for reducibility, thereby providing an alternative to Girard's proof using proof-nets.
Reviewed Works:Andrew Hodges, Rolf Herken, Alan Turing and the Turing Machine.Stephen C. Kleene, Turing's Analysis of Computability, and Major Applications of it.Robin Gandy, The Confluence of Ideas in 1936.Solomon Feferman, Turing in the Land of O.Martin Davis, Esther R. Phillips, Mathematical Logic and the Origin of Modern Computers.
A universal Horn sentence in the language of polynomial-time computable combinatorial functions of natural numbers is true for the natural numbers if, and only if, it is true for PETs of p-time p-isolated sets with functions induced by fully p-time combinatorial operators.