## Theories of ComputabilityBroad in coverage, mathematically sophisticated, and up to date, this book provides an introduction to theories of computability. It treats not only "the" theory of computability (the theory created by Alan Turing and others in the 1930s), but also a variety of other theories (of Boolean functions, automata and formal languages) as theories of computability. These are addressed from the classical perspective of their generation by grammars and from the more modern perspective as rational cones. The treatment of the classical theory of computable functions and relations takes the form of a tour through basic recursive function theory, starting with an axiomatic foundation and developing the essential methods in order to survey the most memorable results of the field. This authoritative account, written by one of the leading lights of the subject, will be required reading for graduate students and researchers in theoretical computer science and mathematics. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Finite Automata and Their Languages | 46 |

Grammars and Their Languages | 99 |

Computable Functions and Relations | 141 |

234 | |

Author Index | 243 |

250 | |

### Other editions - View all

### Common terms and phrases

algebraic alphabet appear application arguments assume automata belongs Boolean functions called clone closed closure complement complete comprises computable consider construct contains context-free contradiction corresponding define definition denote derivation described determine deterministic dyadic element empty encoding equivalence example Exercise exists extended fact Finally finite finite automaton function f given gives grammar homomorphism identifier identities implies indices infinite isomorphic language lattice least Lemma letters linear logical machine marks monadic monoid natural numbers notion observe obtained occurrences operations pair partial function permutation position possible present problems productions programs proof properties Proposition prove questions recognized recursive function recursively enumerable recursively enumerable sets reflexive regular expression relation replacement respectively result satisfies sequence smallest stage subset Suppose symbol T-degree Theorem theory transition unique variables word write yields