Skip to Content

Combinatory Logic

Pure, Applied and Typed

By Katalin Bimbó

Chapman and Hall/CRC – 2011 – 357 pages

Series: Discrete Mathematics and Its Applications

Purchasing Options:

  • Add to CartHardback: $109.95
    978-1-43-980000-3
    July 26th 2011

Description

Combinatory logic is one of the most versatile areas within logic that is tied to parts of philosophical, mathematical, and computational logic. Functioning as a comprehensive source for current developments of combinatory logic, this book is the only one of its kind to cover results of the last four decades. Using a reader-friendly style, the author presents the most up-to-date research studies. She includes an introduction to combinatory logic before progressing to its central theorems and proofs. The text makes intelligent and well-researched connections between combinatory logic and lambda calculi and presents models and applications to illustrate these connections.

Reviews

For beginners, it is a compact introduction, including exercises, to the classical syntactic theory of combinators with some pointers to their models and their relation with ?-calculus. More advanced readers may find in the book much information on the connections between combinators and non-classical and substructural logics that are now a prominent topic in several areas, from philosophical logic to theoretical computer science, information that is mostly scattered through the research literature.

—MATHEMATICAL REVIEWS, 2012

One of the commendable aspects of the book is its extensive and up-to-date bibliography, which deals with CL and other relevant topics in logic; it will surely aid many readers who may need to brush up on background information in the course of their study.

—Computing Reviews, 2012

Contents

Preface

Elements of combinatory logic

Objects, combinators and terms

Various kinds of combinators

Reductions and combinatory bases

Main theorems

Church–Rosser property

Normal forms and consistency

Fixed points

Second fixed point theorem and undecidability

Recursive functions and arithmetic

Primitive and partial recursive functions

First modeling of partial recursive functions in CL

Second modeling of partial recursive functions in CL

Undecidability of weak equality

Connections to l-calculi

l-calculi: L

Combinators in L

Back and forth between CL and L

(In)equational combinatory logic

Inequational calculi

Equational calculi

Models

Term models

Operational models

Encoding functions by numbers

Domains

Models for typed CL

Relational models

Dual and symmetric combinatory logics

Dual combinators

Symmetric combinators

Structurally free logics

Applied combinatory logic

Illative combinatory logic

Elimination of bound variables

Typed combinatory logic

Simply typed combinatory logic

Intersection types for combinators

Appendix

Elements of combinatory logic

Main theorems

Recursive functions and arithmetic

Connections to l-calculi

(In)equational combinatory logic

Models

Dual and symmetric combinatory logic

Applied combinatory logic

Typed combinatory logic

Bibliography

List of Symbols

Index

Author Bio

Katalin Bimbo is an assistant professor in the Department of Philosophy at the University of Alberta in Edmonton, Canada.

Name: Combinatory Logic: Pure, Applied and Typed (Hardback)Chapman and Hall/CRC 
Description: By Katalin Bimbó. Combinatory logic is one of the most versatile areas within logic that is tied to parts of philosophical, mathematical, and computational logic. Functioning as a comprehensive source for current developments of combinatory logic, this book is the only...
Categories: Algorithms & Complexity, Set Theory