Automata, Computability and Complexity

What Hacker News says

1. nyrikkiMay 2023
   While it may not be the _best_ this book is available from the author online.

   Elaine Rich's textbook "Automata, Computability and Complexity: Theory & Applications" https://www.cs.utexas.edu/~ear/cs341/automatabook/index.html

   Useful because it covers non-deterministic Turing Machines complexity classes like BPP,ZPP,RP,etc.. that you would run into Monte Carlo methods etc. As the only Non-deterministic Turing machine most people have been introduced to is the maximally lucky guesser from NP's definition it can help with practical solutions.

   Unfortunately it doesn't have bounded-error quantum polynomial time (BQP) which would help set expectations for quantum supremacy.

   Show morethread
2. groovy2shoesApr 2013
   I agree - the automata, computability, and complexity course I took at university was both eye-opening and fun. I'd recommend a course in discrete mathematics beforehand.

   Furthermore, most CS grads I know would benefit from some statistics knowledge. I've even found physics, linear algebra, and biology (specifically genetics) very useful on the job.

   I see academic subjects the same way many people see programming languages -- they're tools. If all you know is programming, everything starts to look like a programming problem. There are other kinds of problems, too, and even as a professional programmer I often stumble across problems where (basic) knowledge in another field has helped immensely.

   Show morethread