Name: Introduction to the theory of computation
ISBN: 9781133187790

Introduction to the theory of computation

Now you can clearly present even the most complex computational theory topics to your students with Sipser’s distinct, market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today’s computational theory course, this highly anticipated revision retains the unmatched clarity and thorough coverage that make it a leading text for upper-level undergraduate and introductory graduate students. This edition continues author Michael Sipser’s well-known, approachable style with timely revisions, additional exercises, and more memorable examples in key areas. A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. This edition’s refined presentation ensures a trusted accuracy and clarity that make the challenging study of computational theory accessible and intuitive to students while maintaining the subject’s rigor and formalism. Readers gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E’s comprehensive coverage makes this an ideal ongoing reference tool for those studying theoretical computing.

What Hacker News says

elricSep 2026

Fiction: Revelation Space by Alastair Reynolds. I love it. Been reading the series out of order for some reason.

Non-fiction: Introduction to the Theory of Computation by Michael Sipser. It's fun. It looks at things like pushdown automata, Turing machines, decidability, ... Not reading it too rigorously, but more exploratively.

thread

skydhashMay 2025

Introduction to the Theory of Computation by Michael Sipser. There's also his course based on the book on YouTube[0].

Language Implementation Patterns by Terence Parr. It avoids the theory in other books, going for a more practical approach.

Then it was just trying a lot of programming paradigms like functional programming with Common Lisp and Clojure, logic programming with Prolog, array and stack programming with Uiua. And reading snippets of books and papers. It was chaotic.

But the most enlightening lesson was: Formalism is the key. You define axioms, specify rules and as long as you stay consistent, it's ok. The important thing is to remember the axioms and understanding the rules.

[0]: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3...

thread

User23Jan 2025

No they really are. Arbitrarily long means "pick a number any number." Infinite means, well infinite. And infinity is always bigger than "pick a number, any number."

I suggest that you read Michael Sipser's Introduction to the Theory of Computation. It's absolutely lovely and an easy read, considering the subject matter. It will help you to understand cardinality (and many other things) in a pragmatic computing science context.

thread

trealiraJun 2024

A finite state machine has a set of input symbols, a set of states, and a transition function, which maps the current state and current input to the next state (and, when programming it, it doesn't have to be a literal function; for example, it could be a 2D array). It also has a start state, and a set of accept states.

It's also common for state machines to have some sort of output; otherwise, all an FSM can do is recognize whether an input string is "good." So, there's also an output function, so that the FSM actually does something while processing the input string. There are two types of FSMs: a Mealy Machine, and a Moore machine. In a Mealy machine, the output function maps the current state and the current input to an output; so, one state could be associated with multiple outputs. In a Moore machine, the output is purely a function of the current state, no matter the input. Usually, a Moore machine has more states than the equivalent Mealy machine. In practice, Moore machines are a lot rarer than Mealy machines.

You can model FSMs in a variety of ways. You could use the state pattern [0]. You could have a table-based state machine; examples in C here [1] [2]. It's also common to model them using a loop and a switch statement with integers to represent the current state - or just use "goto" to go to the next state, if it's available in your language.

Also, this is tangential, but something nice about coroutines is that they save can you from writing an explicit state machine, as the state is implicit in your code. One example of this is how it's easier to write iterators as coroutines that yield results as they run, rather than as structures that update themselves based on their current state, transition to the next state, and yield a result.

So far, what I've covered is basically a deterministic finite automaton (DFA). There are also non-deterministic finite automata (NDFAs), which are used to implement regular expressions (at least when regular expressions aren't extended to require more powerful recognizers) [3], as well as pushdown automata (PDAs), which are basically finite automata with a stack, and can parse e.g. programming languages. Finally, there are Turing machines.

For theory on that, I'd recommend reading Sipser's Introduction to the Theory of Computation. If you look up the book on Google, it's not difficult to find a PDF of it.

[0]: https://refactoring.guru/design-patterns/state

[1]: https://nullprogram.com/blog/2020/12/31

[2]: https://ideone.com/94U6aJ (this one removes C-style comments from source code - I didn't make it)

[3]: https://swtch.com/~rsc/regexp/regexp1.html

thread

dysocoJun 2024

I believe I used Introduction to the Theory of Computation by Sipser for this and it's probably the one textbook most universities are going to use.

Maybe for more in depth reference about the algorithms at play Introduction to Algorithms (Cormen) will complement nicely; I don't remember how much Sipser goes into describing the algos.

thread

dlorancJun 2024

Books I have and recommend:

Introduction to the theory of computation - Michael Sipser

Computational complexity - Arora, Barak

Computational Complexity - Christos H. Papadimitriou

Computers and intractability - Michael R. Garey, David S. Johnson

thread