Theory of computation

What Hacker News says

1. sky2224Jun 2024
   As someone else said already: Theory of Computation by Sipser is the go to intro book for this.

   I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory.

   Sipser also has corresponding lectures that are available for free on YouTube here: https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzp....

   thread
2. bo1024May 2023
   Lots of favorite math books! Not as many programming. Maybe I'd recommend Sipser's Intro to the Theory of Computation?
   thread
3. agomez314Oct 2022
   - Conquest: Cortes, Montezuma, and the Fall of Old Mexico by Hugh Thomas , because he brings history to life and the story of the Spanish and the Mexica is stranger than fiction, more subtle and terrible than you might think, and has many lessons on human behavior applicable to today.

   - Ecclesiastes by Qoheleth: In my opinion, superior to Marcus Aurelius' Meditations. "Go, eat your bread with enjoyment, and drink your wine with a merry heart; for God has already approved what you do. Let your garments be always white; let not oil be lacking on your head. Enjoy life with the wife whom you love, all the days of your vain life which he has given you under the sun, because that is your portion in life and in your toil at which you toil under the sun. Whatever your hand finds to do, do it with your might; for there is no work or thought or knowledge or wisdom in Sheol, to which you are going." (Eccles 9:11)

   - Amusing ourselves to death by Neil Postman: We thought we had to worry about 1984 and big brother. We were wrong. We are living in Huxley's Brave New World where digital media has made us dumber, distracted and cut our connections with one other. Our smartphones substitute rosaries and entertainment becomes the dogma.

   - Structure and Intepretation of Computer Programs by Hal Abelson and Gerlad J. Sussman: Need I say more? This books makes me fall in love all over again with programming every time I pick it up.

   - Nichomachean Ethics by Aristotle: What does it mean to live well? How can we be happy? Aristotle makes the striking claim that everyone knows how to be happy, but we have to create the habits that are in accord with reason and right judgement in order to get there. Also, happiness is not a state but rather the result of our active will and right ordering of desire. Required reading for any political leader.

   - Theory of Computation by Michael Sipser: Javascript frameworks come and go, language standards change, Computer platforms rise and fall, but math and the underling concepts of computation stay the same. Knowing what computation is, what its properties are, etc. will not only make you a better programmer but a better thinker. Church-Turing Thesis essential reading for anyone serious about algorithm design and analysis.

   Show morethread
4. OJFordJun 2022
   Sipser's Theory of Computation

   Spence's Information Visualisation

   thread
5. OJFordFeb 2022
   The Annotated Turing by Petzold (On Computable Numbers broken down, annotated, explained, and talked around. Would recommend to anyone interested in CS but without (yet) having formally studied it. I read it in sixth form, and it probably swung me more towards CS from my since-childhood intention of studying electronics. (Ended up doing a mix, but applied to some straight CS too.))

   Theory of Computation by Sipser. (More subject specific and just a textbook really, I just thought it was a really great one and was able to read it ahead of my most relevant course.)

   Show morethread
6. beatgammitAug 2019
   Do you need it for the type of work you want? If not, you probably don't need to learn it.

   That being said, if you want to get into CS, I recommend getting a textbook or two about computational complexity (big-O notation) and the theory of computation (nondeterministic finite automata and regular expressions, stack machines, and Turing machines). I liked "Theory of Computation" by Michael Sipser for the second topic (didn't like my textbook for the first), though it's very dense so you may want to look into additional material if you want a gentler introduction.

   Honestly, you can probably find everything online. The main things to look for are:

   - big-O notation (how many steps it takes to solve a problem given some input size) - data structures (linked lists, b-trees, and hash maps are the big ones) - the list of terms above

   Work out some proofs until you feel comfortable with the material.

   But it really doesn't matter of you just want to do web stuff. Most of the hard problems have been solved by the standard library or database you use, so unless you want to work on those, you can choose to be ignorant of the inner workings. I'm the type that doesn't like to not understand something, but I have plenty of friends who care more about other things than learning CS/EE stuff that isn't practical to their line of work.

   Show morethread