## Computability theory: concepts and applications |

### What people are saying - Write a review

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

### Contents

Introduction | 1 |

Turing machines | 11 |

Turing machines as recognisers | 27 |

Copyright | |

9 other sections not shown

### Common terms and phrases

alphabet argument arithmetic assertion axiomatic behaviour binary canonical ordering Cantor's cell Chapter Church-Turing hypothesis cloc Computability Theory Computer Science concept consider construct a Turing contains Continuum Hypothesis contradiction decision problem defined definition denote described effective algorithms encoding enumeration Example false finite control finite language finite number follows formal Godel's results goto halting problem halts and accepts halts and rejects halts on input IMPOS(M,w input word instantaneous description Lemma Ln is recursive Markov algorithms models of computation moves natural numbers non-deterministic Turing machine output partial recursive function Post machine Post system Post's Correspondence Problem primitive recursive probabilistic probabilistic Turing machine proof propositions provable proved r.e. languages real number recursive languages register machines Rice's Theorem scanned sentence sequence simulates solve string subset Suppose test instruction tion total recursive functions true Turing machine accepting Turing machine code Turing machine program undecidable Unlimited register machines