What people are saying - Write a review
We haven't found any reviews in the usual places.
Turing Machines and Computable Functions
4 other sections not shown
Other editions - View all
algorithm alphabet argument auxiliary symbols axioms binary block constructed contains context-free grammar context-free language context-sensitive grammar context-sensitive languages corresponding counterexample deduction defined definition denote derivation deterministic diagram effective enumeration effective procedure element empty stack equivalent erases Exercise false Figure final finite acceptor finite automaton finite number finite set first-order arithmetic given Godel number halting problem Hence induction infinite input string input tape instantaneous description leftmost length length-increasing grammar linear bounded automaton machine of example machine to compute Markov algorithm mathematical natural numbers non-deterministic noughts operations output partial computable function partial recursive function possible predicate logic primitive recursive functions problem productions proof provable pushdown acceptor pushdown automata quintuples R(xi real numbers recursively enumerable sets regular expressions relation represented rules sentence logic sequence of strings set of strings shown sub-routine subset terminal theorem theory track true Turing acceptor Turing machine word xk,y