Introduction to Theory of Computation

Livro digital

Título:
Introduction to Theory of Computation

Autor:
Anil Maheshwari, Michiel Smid

Categoria:
Tecnologia > Geral

Doador:
Raffaello D. N.

Sinopse:
Most programmers rely on computational tools without questioning what can—and cannot—be computed. The journey from a simple finite automaton controlling a toll gate to the universal power of a Turing machine reveals the precise mathematical boundary between the solvable and the unsolvable. This textbook builds the theory of computation from the ground up: deterministic and nondeterministic finite automata, regular expressions and the pumping lemma, context-free grammars and pushdown automata, and Turing machines culminating in the Church-Turing thesis. Along the way, formal proof techniques—from induction to the pigeonhole principle—are developed as practical tools rather than abstract rituals, with exercises reinforcing each concept. Written by two Carleton University computer scientists, the presentation balances formal rigor with worked examples that show why these ideas matter. You will come away understanding not just how to classify problems by complexity, but why some questions are fundamentally beyond the reach of any algorithm.