## Computation: Computability, Similarity, and Duality |

### What people are saying - Write a review

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

### Contents

FINITE AUTOMATA AND COMPUTABILITY | 5 |

The Turing Machine | 17 |

Recursive Functions | 27 |

Copyright | |

35 other sections not shown

### Common terms and phrases

algorithm binary string Boolean bounding functions called choice complexity choice sequence coding computational models configuration contents corresponding defined DEFINITION denoted deterministic directed graph edge EXAMPLE Exercises f,g)-h reference machine fan-out halts index registers input gates input head input length input tape head input word integer labelled binary tree language accepted leaf labelled Lemma log-space constructible log-space reduction logical computational types LSTM of phase move function multitape NDFA nice pair node non-deterministic Turing machine normal system obtain Obviously output tape parallel path polynomial polynomially related PRAM primitive recursive function problem processors Prove q e Q recursive function recursively enumerable reference TM regular expression rejecting reversal complexity satisfies restriction sequential simulate space complexity square step stored Suppose that f,g THEOREM TM of type total number type TM unary representation uniform circuit vector machine vertex width write