Proofs and algorithms an introduction to logic and computability / Gilles Dowek.
| Author/creator | Dowek, Gilles |
| Format | Electronic |
| Publication Info | London ; New York : Springer, |
| Description | xii, 155 p. : ill. ; 24 cm. |
| Supplemental Content | Full text available from Springer Books |
| Supplemental Content | Full text available from Springer Nature - Springer Computer Science eBooks 2011 English International |
| Subjects |
| Series | Undergraduate topics in computer science, 1863-7310 Undergraduate topics in computer science. ^A787640 |
| Contents | Part. 1. Proofs: -- 1. Predicate logic. --Inductive definitions -- Languages -- The languages of predicate logic -- Proofs -- Examples of theories -- Variations on the principle of the excluded middle -- 2. Models. -- The notion of a model -- The Soundness Theorem -- The Completeness Theorem -- Other applications of the notion of model -- Part 2. Algorithms: -- 3. Computable functions. -- Computability over lists and trees -- Eliminating recursion -- Programs -- 4. Computation as a sequence of small steps. -- Rewriting -- The Lambda-Calculus -- Turing Machines -- Part 3. Proofs and algorithms: -- 5. Church's Theorem. -- The notion of reduction -- Representing programs -- Church's Theorem -- Semi-decidabilty -- Gödel's First Incompleteness Theorem -- 6. Automated theorem proving. -- Sequent Calculus -- Proof search in the sequent Calculus without cuts -- 7. Decidable theories -- 8. Constructivity -- 9. Epilogue. |
| Bibliography note | Includes bibliographical references (p. 151) and index. |
| Access restriction | Available only to authorized users. |
| Technical details | Mode of access: World Wide Web |
| Genre/form | Electronic books. |
| LCCN | 2011282450 |
| ISBN | 9780857291202 |
| ISBN | 0857291203 |