Proofs and algorithms. An introduction to logic and computability

DOI10.1007/978-0-85729-121-9zbMath1230.03001OpenAlexW2482267932MaRDI QIDQ625290

Gilles Dowek

Publication date: 15 February 2011

Published in: Undergraduate Topics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-0-85729-121-9

zbMATH Keywords

algorithmcompletenessdecidabilityTuring machinerewriting systemhalting problemlambda calculussoundnessproofpredicate logicmodel

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Undecidability and degrees of sets of sentences (03D35) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Logic in computer science (03B70) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Recursive functions and relations, subrecursive hierarchies (03D20) Proof theory in general (including proof-theoretic semantics) (03F03) Turing machines and related notions (03D10) Combinatory logic and lambda calculus (03B40) Basic properties of first-order languages and structures (03C07) General topics in the theory of algorithms (68W01)

Related Items

Transforming orthogonal inductive definition sets into confluent term rewrite systems ⋮ Clausal presentation of theories in deduction modulo