Reddit reviews Introduction to the Theory of Computation
We found 21 Reddit comments about Introduction to the Theory of Computation. Here are the top ones, ranked by their Reddit score.
Reddit reviews Introduction to the Theory of ComputationWe found 21 Reddit comments about Introduction to the Theory of Computation. Here are the top ones, ranked by their Reddit score.
Introduction to the Theory of Computation
he lost me when he said this about GEB
> If you only read one book on this list, it should be this one.
seriously? it's not that i don't appreciate the sentiment, but things douglas hofstadter thinks are neat is no substitute for any single book on the rest of the list unless you
for my part, i'd add sipser's computation book and why not throw in some ken thompson in there as an amuse bouche?
Introduction to the Theory of Computation is one of my favourites
I would guess that career prospects are a little worse than CS for undergrad degrees, but since my main concern is where a phd in math will take me, you should get a second opinion on that.
Something to keep in mind is that "higher" math (the kind most students start to see around junior level) is in many ways very different from the stuff before. I hated calculus and doing calculations in general, and was pursuing a math minor because I thought it might help with job prospects, but when I got to the more abstract stuff, I loved it. It's easily possible that you'll enjoy both, I'm just pointing out that enjoying one doesn't necessarily imply enjoying the other. It's also worth noting that making the transition is not easy for most of us, and that if you struggle a lot when you first have to focus a lot of time on proving things, it shouldn't be taken as a signal to give up if you enjoy the material.
This wouldn't be necessary, but if you like, here are some books on abstract math topics that are aimed towards beginners you could look into to get a basic idea of what more abstract math is like:
Different mathematicians gravitate towards different subjects, so it's not easy to predict which you would enjoy more. I'm recommending these five because they were personally helpful to me a few years ago and I've read them in full, not because I don't think anyone can suggest better. And of course, you could just jump right into coursework like how most of us start. Best of luck!
(edit: can't count and thought five was four)
sipser (I have the first edition which you can get on the cheap, it's very good.)
AIMA
Dragon
Naturally, TAOCP.
Many will also recommend SICP, though I'm not quite sure that's what you're angling at here, it's probably worth browsing online to see.
Ah...Sipser.
Sure! There is a lot of math involved in the WHY component of Computer Science, for the basics, its Discrete Mathematics, so any introduction to that will help as well.
http://www.amazon.com/Discrete-Mathematics-Applications-Susanna-Epp/dp/0495391328/ref=sr_sp-atf_title_1_1?s=books&ie=UTF8&qid=1368125024&sr=1-1&keywords=discrete+mathematics
This next book is a great theoretical overview of CS as well.
http://mitpress.mit.edu/sicp/full-text/book/book.html
That's a great book on computer programming, complexity, data types etc... If you want to get into more detail, check out: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/0534950973
I would also look at Coursera.org's Algorithm lectures by Robert Sedgewick, thats essential learning for any computer science student.
His textbook: http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X/ref=sr_sp-atf_title_1_1?s=books&ie=UTF8&qid=1368124871&sr=1-1&keywords=Algorithms
another Algorithms textbook bible: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_sp-atf_title_1_2?s=books&ie=UTF8&qid=1368124871&sr=1-2&keywords=Algorithms
I'm just like you as well, I'm pivoting, I graduated law school specializing in technology law and patents in 2012, but I love comp sci too much, so i went back into school for Comp Sci + jumped into the tech field and got a job at a tech company.
These books are theoretical, and they help you understand why you should use x versus y, those kind of things are essential, especially on larger applications (like Google's PageRank algorithm). Once you know the theoretical info, applying it is just a matter of picking the right tool, like Ruby on Rails, or .NET, Java etc...
How formal do you mean? If you're interested in the theory of computer science, have a read of Sipser's Introduction to the Theory of Computation (or on Amazon - get it 2nd hand). This is a very theoretical book though, and most CS undergrad courses will only cover this type of content as a small part of the subject matter taught, so don't be put off if it doesn't immediately appeal or make sense!
Edit - links.
It may be a big of a tough slog, but Sipser's Introduction to the Theory of Computation is great. The stuff on computability theory might be right up your alley, and even if you only make it through the chapter on deterministic finite automata you likely will be better at crafting a regular expression than many of my CS student peers.
Surprisingly enough, the book should be able to help you make sense out of that last sentence within 100 pages requiring only a bit of understanding of proofs. I think if you've got predicate logic under your belt you pretty much have all you need.
I'm sure any computational theory book will work for you. Here's the one I used: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/0534950973
It goes through deterministic and nondeterministic automata, context free grammars, turing machines, and all that stuff.
I would recommend (and I find that I recommend this book about every 3rd thread which should say something) a book on theoretical computer science. The book is all about the beautiful mathematics that underlie all of computing.
Computers keep getting faster and faster, but are there are any questions that we can never answer with a computer no matter how fast? Are there different types of computers? Can they answer different types of questions?
What about how long it takes to answer a question? Are some questions fundamentally harder than others? Can we classify different problems into how hard they are to solve? Is it always harder to find a solution to a problem than to check that a solution is correct? (this is the gist of the famous P=NP problem )
The book has essentially no prerequisites and will take you through (initially) basic set theory moving on to logic and then the fun stuff. Every proof is incredibly clearly written with a plain English introduction of what the author is about to do before the technical bits.
The only downsides are that is quite expensive and you might have trouble finding it unless you have access to a university library/bookshop.
Good luck with your love of mathematics!
Edit: lol the book... Introduction to the theory of computation - Sipser
I don't know about other schools but my CS program required discrete math and automata theory to complete the major. I really enjoyed automata theory but I can imagine it being kind of tough to get into outside of a classroom setting. Having said that, I would highly recommend this book if you're trying to learn some of this stuff on your own.
Then you need to learn about The Theory of Computation.
This will give you historical insight on how scientists thought of computing; particularly defining the powers of computation and language.
As for languages, the best way is to probably look at historical papers on language design on topics such as LISP, type theory, lambda calculus, OOP/OOD, etc. But a book that gives a good starting point would probably be Programming Langauge Pragmatics.
I like the one by Sipser https://www.amazon.com/gp/product/0534950973/ref=dbs_a_def_awm_bibl_vppi_i1
That's not an algorithms. No, sirree, what you've got there is a theoretical computer science class. This is the Sipser on the board.
Oi. Disclaimer: I haven't bought a book in the field in a while, so there might be some new greats that I'm not familiar with. Also, I'm old and have no memory, so I may very well have forgotten some greats. But here is what I can recommend.
I got my start with Koblitz's Course in Number Theory and Cryptography and Schneier's Applied Cryptography. Schneier's is a bit basic, outdated, and erroneous in spots, and the guy is annoying as fuck, but it's still a pretty darned good intro to the field.
If you're strong at math (and computation and complexity theory) then Oded Goldreich's Foundations of Cryptography Volume 1 and Volume 2 are outstanding. If you're not so strong in those areas, you may want to come up to speed with the help of Sipser and Moret first.
Also, if you need to shore up your number theory and algebra, Victor Shoup is the man.
At this point, you ought to have a pretty good base for building on by reading research papers.
One other note, two books that I've not looked at but are written by people I really respect Introduction to Modern Cryptography by Katz and Lindell and Computational Complexity: A Modern Approach by Arora and Barak.
Hope that helps.
My local used book store has a copy of Sipser for $15 that I've been meaning to pick up. Considering the $143 price tag on Amazon, it's a pretty good bargain. I just don't know whether it's 1st or 2nd edition. Anyone have any idea if there are major differences?
Depending on the amount of energy you want to put into this: "Introduction to Lambda Calculus" by Henk Barendegt et al. is great ((http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf).
Study the proofs and do the exercises and you will learn a ton, quickly. You can also read "proposition as types" by Philip Wadler (http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf) and pick up the "Introduction to the Theory of Computation" book (https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/0534950973/)
Of course you don't need to read all of this to get a basic understanding of lambda calculus but if you want to understand for "real" so it sticks.
Work hard and you'll get there. I preferred the applied side of things, but if I just stuck with pure math I think I would have eventually gotten a tenure track position in the mathematics side of things.
My favorite book to this day, for a beginners course in Computational complexity is still, Michael Sipser's Introduction to theory of computation, I highly recommend it. It might be a little too easy for you if you already have a base, let me know and I'll recommend books more advanced.
Here is a link to the book on amazon, although any big college library should have it, if not just have them order it for you. I've gotten my college's library to buy so many books that I wanted to read, but not spend money on, you'd be surprised at how responsive they are to purchasing requests from PhD candidates.
It's not free (in fact it's sickeningly expensive) but Sipser [amazon.com] is a very self-teachable (self-learn-from-able? :) ) text covering automata theory, computability theory, and complexity theory.
College books are also much more expensive in the USA than in Europe.
For example:
$152.71
VS
£43.62($68.03)
$146.26 VS
£44.34($69.16)