#76 in Computers & technology books
Use arrows to jump to the previous/next product
Reddit mentions of Introduction to the Theory of Computation
Sentiment score: 22
Reddit mentions: 37
We found 37 Reddit mentions of Introduction to the Theory of Computation. Here are the top ones.
or
- Used Book in Good Condition
Features:
Specs:
| Height | 9.5 Inches |
| Length | 6.5 Inches |
| Number of items | 1 |
| Weight | 1.64905771976 Pounds |
| Width | 1 Inches |
Textbooks?
I'm sort of in the same boat as you, except with an aero and physics background rather than EE. My approach has been pretty similar to yours--I found the textbooks used by my alma mater, compared to texts recommended by MIT OCW and some other universities, looked at a few lists of recommended texts, and looked through similar questions on Reddit. I found most areas have multiple good texts, and also spent some time deciding which ones looked more applicable to me. That said, I'm admittedly someone who rather enjoys and learns well from textbooks compared to lectures, and that's not the case for everyone.
Here's what I gathered. If any more knowledgeable CS guys have suggestions/corrections, please let me know.
Full disclosure: I haven't actually read more than the preface of any of those books. Software engineering topics are more directly applicable to me than CS topics right now, so here are some that I've actually started reading:
Without knowing much about you, I can't tell how much you know about actual math, so apologies if it sounds like I'm talking down to you:
When you get further into mathematics, you'll find it's less and less about doing calculations and more about proving things, and you'll find that the two are actually quite different. One may enjoy both, neither, or one, but not the other. I'd say if you want to find out what higher level math is like, try finding a very basic book that involves a lot of writing proofs.
This one is aimed at high schoolers and I've heard good things about it, but never used it myself.
This one I have read (well, an earlier edition anyway) and think is a phenomenal way to get acquainted with higher math. You may protest that this is a computer science book, but I assure you, it has much more to do with higher math than any calculus text. Pure computer science essentially is mathematics.
Of course, you are free to dive into whatever subject interests you most. I picked these two because they're intended as introductions to higher math. Keep in mind though, most of us struggle at first with proofwriting, even with so-called "gentle" introductions.
One last thing: Don't think of your ability in terms of your age, it's great to learn young, but there's nothing wrong with people learning later on. Thinking of it as a race could lead to arrogance or, on the other side of the spectrum, unwarranted disappointment in yourself when life gets in the way. We want to enjoy the journey, not worry about if we're going fast enough.
Best of luck!
Google hasn't been helpful because no such algorithm exists. Check out Rice's Theorem for the impossibility.
edit:
Let S be the set of languages that you can reduce SAT to in polynomial time.
SAT is clearly in S, and we know some machine recognizes it.
The empty language is not in S (even if P=NP, so that SAT is P-complete), and we know some machine recognizes it.
By Rice's Theorem, no machine decides, when given a machine as input, whether that machine recognizes a language in S.
(we assume that the "any custom problem" input is as a machine encoding)
edit2:
I see that you make a lot of questions about computational complexity, but do not have a good foundation. Many things you propose or ask already have known impossibility results. May I suggest you have a look at Sipser (https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X)? That will give you a better understanding of computability and complexity to understand the feedback you're getting.
A few of my favorites:
Sipser's Introduction to the Theory of Computation is an excellent book with three major parts:
Each part builds on the previous. I highly recommend working through it.
So, when I was younger, I did attend one computer science related camp,
https://www.idtech.com
They have a location at Emory (which I believe I did one year) that was ok (not nearly as "nerdy"), and one at Boston which I really enjoyed (perhaps because I had to sleep on site). That being said, the stuff I learned there was more in the areas of graphic design and/or system administration, and not computer science. They are also quite expensive for only 1-2 weeks of exposure.
I felt it was a good opportunity to meet some very smart kids though, and it definitely lead me to push myself. Knowing and talking to people that are purely interested in CS, and are your age, is quite rare in high school. I think that kind of perspective can make your interests and hobbies seem more normal and set a much higher bar for what you expect for yourself.
On the other side of things, I believe that one of the biggest skills in any college program is an openness to just figure something out yourself if it interests you, without someone sitting there with you. This can be very helpful in life in general, and I think was one of the biggest skills I was missing in high school. I remember tackling some tricky stuff when I was younger, but I definitely passed over stuff I was interested in just because I figured "thats for someone with a college degree". The fact is that experience will make certain tasks easier but you CAN learn anything you want. You just may have to learn more of the fundamentals behind it than someone with more experience.
With that in mind, I would personally suggest a couple of things which I think would be really useful to someone his age, give him a massive leg up over the average freshman when he does get to college, and be a lot more productive than a summer camp.
One would be to pick a code-golf site (I like http://www.codewars.com) and simply try to work through the challenges. Another, much more math heavy, option is https://projecteuler.net. This, IMO is one of the best ways to learn a language, and I will often go there to get familiar with the syntax of a new language. I think he should pick Python and Clojure (or Haskell) and do challenges in both. Python is Object Oriented, whilst Clojure (or Haskell) is Functional. These are two very fundamental and interesting "schools of thought" and if he can wrap his head around both at this age, that would be very valuable.
A second option, and how I really got into programming, is to do some sort of web application development. This is pretty light on the CS side of things, but it allows you to be creative and manage more complex projects. He could pick a web framework in Python (flask), Ruby (rails), or NodeJS. There are numerous tutorials on getting started with this stuff. For Flask: http://blog.miguelgrinberg.com/post/the-flask-mega-tutorial-part-i-hello-world. For Rails: https://www.railstutorial.org. This type of project could take a while, there are a lot of technologies which interact to make a web application, but the ability to be creative when designing the web pages can be a lot of fun.
A third, more systems level, option (which is probably a bit more opinionated on my part) is that he learn to use Linux. I would suggest that he install VirtualBox on his computer, https://www.virtualbox.org/wiki/Downloads. He can then install Linux in a virtual machine without messing up the existing OS (also works with Mac). He COULD install Ubuntu, but this is extremely easy and doesn't really teach much about the inner workings. I think he could install Arch. https://wiki.archlinux.org. This is a much more involved distribution to install, but their documentation is notoriously good, and it exposes you to a lot of command line (Ubuntu attempts to be almost exclusively graphical). From here, he should just try to use it as much as possible for his daily computing. He can learn general system management and Bash scripting. There should be tutorials for how to do just about anything he may want. Some more advanced stuff would be to configure a desktop environment, he could install Gnome by default, it is pretty easy, but a lot of people really get into this with more configurable ones ( https://www.reddit.com/r/unixporn ). He could also learn to code and compile in C.
Fourth, if he likes C, he may like seeing some of the ways in which programs which are poorly written can be broken. A really fun "game" is https://io.smashthestack.org. He can log into a server and basically "hack" his way to different levels. This can also really expose you to how Linux maintains security (user permissions, etc. ). I think this would be much more involved approach, but if he is really curious about this stuff, I think this could be the way to go. In this similar vein, he could watch talks from Defcon and Chaos Computer Club. They both have a lot of interesting stuff on youtube (it can get a little racy though).
Finally, there are textbooks. These can be really long, and kinda boring. But I think they are much more approachable than one might think. These will expose you much more to the "Science" part of computer science. A large portions of the classes he will take in college look into this sort of stuff. Additionally, if he covers some of this stuff, he could look into messing around with AI (Neural Networks, etc.) and Machine Learning (I would check out Scikit-learn for Python). Here I will list different broad topics, and some of the really good books in each. (Almost all can be found for free.......)
General CS:
Algorithms and Data Structures: https://mitpress.mit.edu/books/introduction-algorithms
Theory of Computation: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Operating Systems: http://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720
Some Math:
Linear Algebra: http://math.mit.edu/~gs/linearalgebra/
Probability and Stats: http://ocw.mit.edu/courses/mathematics/18-05-introduction-to-probability-and-statistics-spring-2014/readings/
I hope that stuff helps, I know you were asking about camps, and I think the one I suggested would be good, but this is stuff that he can do year round. Also, he should keep his GPA up and destroy the ACT.
The first step to doing research is ingesting whatever knowledge already exists. With that in mind:
What do you mean by "I want to be computer scientist?" Do you want to do research for a living, e.g, work in academia or for a lab? Or is your goal more along the lines of, "I want to learn more about computer science?" If the former, you're not going to get far without a degree, usually a Ph.D is necessary. If the latter is your goal then the 'traditional' math subjects would be 'discrete' subjects like probability and combinatorics. Linear algebra is heavily used in machine learning, and I believe PDEs are used as well.
On the computer science side, computability theory and computational complexity are necessary. Sipser is the standard for computability theory, and I like Arora/Barak for complexity (I don't necessarily recommend buying on amazon; that price for Sipser is outrageous).
My compilers course in college used the Dragon Book, which is one of the more quintessential books on the subject.
​
But you might also consider Basics of Compiler Design which is a good and freely available resource.
​
I'd also suggest that you have familiarity with formal languages and automata, preferably through a Theory of Computation course (Sipser's Introduction to the Theory of Computation is a good resource). But these texts provide a brief primer.
It's Problem 7.29 in the third edition of Michael Sipser's Introduction to the Theory of Computation (you can find it by searching for "coloring" when using the preview function on Amazon). It's also in The design and analysis of computer algorithms by Aho, Hopcroft and Ullman as Theorem 10.12, though the proof there seems a little different from what you've sketched. (I hope that the Google Books link works. Sometimes it won't show the right preview.)
> Would you say there's more opportunity working exclusively front end and design to exercise nfp creativity or novelty?
NFP creativity and novelty in the sense that Ne has free range, period? Sure, you get more of that in web design and even more of that as to step further and further away from the sciences. There is tons of creativity in real software engineering where you can be creative to solve actually challenging problems, not figuring out what color you'd like a button to be. To me, that's not creativity – or it's a lesser version. Creativity in problem solving is much more interesting. The way I see it is like when I was in music school and all the SFs were bitching about music theory and how they thought it limited their ability to "be creative". Such bullshit. It only exposes their lack of creativity. So you're saying that someone like Chopin who wrote amazing pieces and abided by the rules of music theory wasn't being creative? Hardly.
> Are you a web dev?
No, I'm a software engineer at an astrodynamics company; I do a lot of orbital mechanics, back-end work with web services, high performance computing, etc.
> By hardcore I meant requiring being meticulous, detail oriented.
I think that the lack of attention to detail is never permissible in either back-end software engineering or front-end web development, honestly.
> One thing I've realized is how shit my high school was at explaining math conceptually. Which I think lead to misconceptions about its use in programming
Well, then read some books on computer science and/or mathematics like this.
I think learning proofs-based calculus and linear algebra are solid places to start. To complete the trifecta, look into Arnold for a more proofy differential equations course.
After that, my suggestions are Rudin and, to build on your CS background, Sipser. These are very standard references, though Rudin's a slightly controversial suggestion because he's notorious for being terse. I say, go ahead and try it, you might find you like it.
As for names of fields to look into: Real Analysis, Complex Analysis, Abstract Algebra, Topology, and Differential Geometry mostly partition the field of mathematics with corresponding undergraduate courses. As for computer science, look into Algorithmic Analysis and Computational Complexity (sometimes sold as a single course called Theory of Computation).
Hi,
You should already know most of the math you need to know from your math major. It helps to know number theory, group theory, and algebraic curves, depending on what you do. Important knowledge is also discrete mathematics: Discrete probability theory, Markov chains, graph theory, logic, proof methods, solving recurrences, etc. are all helpful tools.
In terms of computer science, it's imperative to know how to program. You can learn a programming language such as Python. Project Euler is a good place to start for a mathematician. Knowledge of algorithms is also important, and you must understand computability and complexity theory.
Stanford's Cryptography I is a good place to start learning cryptography. I think you can go ahead and start the course without attempting prerequisites and see where you get stuck to go and learn what is required of you.
Computer Science is a pretty big field, so "strong foundation" can mean different things to different people.
You will definitely want the following:
For algorithms and data structures, a very commonly used textbook is Cormen.
For computability, Sipser.
Operating Systems I don't remember off the top of my head.
That said, you are probably much better off finding a high-quality university course that is based on these textbooks instead of trying to read them cover-to-cover yourself. Check out lecture series from places like MIT on youtube or whatever.
After that, you can take an Intro to Artificial Intelligence, or Intro to Communication Networks, or any other intro-level course to a more specific sub-area. But if you lack basis in computability to the point where you don't know what an NP-Complete problem is, or have no idea what a Binary Search Tree is, or do not know what an Approximation Algorithm is, then it would be hard to say you have a strong foundation in CS.
Just my 2 cents: The Stanford Algorithms class is more about designing algorithms. The Princeton Algorithms class is more about implementation and real world testing.
The FAQ at the bottom:
How does Algorithms: Design and Analysis differ from the Princeton University algorithms course?
The two courses are complementary. That one emphasizes implementation and testing; this one focuses on algorithm design paradigms and relevant mathematical models for analysis. In a typical computer science curriculum, a course like this one is taken by juniors and seniors, and a course like that one is taken by first- and second-year students.
As a computer science student, I would encourage you to pick up a book on Discrete Mathematics, and pick up Robert Sedgwick's Algorithm's textbook. Sedgwick's Algorithms book is more about implementing algorithms, compared to CLRS, which is another algorithms textbook written by some very smart guys. CLRS is far more in depth.
I took a Data Structures and Algorithms class recently, we used Sedgwick's textbook. I will be taking another ALgorithms & Design class later using CLRS.
Books:
http://www.amazon.com/Discrete-Mathematics-Applications-Susanna-Epp/dp/0495391328/ref=sr_1_1?s=books&ie=UTF8&qid=1372267786&sr=1-1&keywords=discrete+mathematics
http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X/ref=sr_1_1?s=books&ie=UTF8&qid=1372267775&sr=1-1&keywords=algorithms
http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1372267766&sr=8-1&keywords=clrs
http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/ref=sr_1_1?s=books&ie=UTF8&qid=1372267798&sr=1-1&keywords=theory+of+computation
The last book is super important for CS students, I would read that front to back as well.
I'm not really good at explaining stuff, but this book is a great resource regarding turing machine and turing completeness: Introduction to the Theory of Computation
Turing machine is a model first proposed by Alan Turing. It's similar to Finite Automaton, but it has unlimited tape memory. Basically, modern computers is an implementation of the Turing Machine. One characteristics of a turing machine is it's possible to use a turing machine to simulate another turing machine.
A programming language is said to be turing complete if it can be used to simulate a turing machine. If you've written a program in a turing complete language, you should be able to translate that program to any turing complete programming language.
So if css become a turing complete language, I imagine people will use it to create crazy stuff such as an x86 emulator.
this is the book you are talking about I am assuming?
I think I am looking for a more advanced book than this. I have already learned most of these topics in my own classes in school. I suppose I would be looking for the books that would be recommended after having learned this book.
For a book, I recommend Michael Sipser's Introduction to the Theory of Computation.
Here, if you can find it somewhere on the internet (cough), this book covers it nicely and is widely used (at least in German universities)
https://www.amazon.de/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
this is the canonical undergrad book
https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Sipser's Introduction to the Theory of Computation is the standard textbook. The book is fairly small and quite well written, though it can be pretty dense at times. (Sipser is Dean of Science at MIT.)
You may need an introduction to discrete math before you get started. In my udergrad, I used Rosen's Discrete Mathematics and Its Applications. That book is very comprehensive, but that also means it's quite big.
Rosen is a great reference, while Sipser is more focused.
If your not afraid of math then I would recommend the books by Robert Sedgewick. His java book really shows off Java. His Algorithms book is a religious experience. And if your feeling masochistic, the Sipser book is well suited.
This book:
http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Is absolutely fantastic
The classic Introduction to the Theory of Computation is quite excellent, though very pricey. Also, I had the pleasure of having a university class that used this book, so having a professor that can clear things up from the book was a big help.
Excellent! I'm glad to know the concept is clear to you.
I would recommend you to using the Lewis & Papadimitriou book as well as the Sipser one: for me, the former is more formal than the latter, that is more didatic (specially for undergraduate students); however, both use a simple language and are very didatic.
My advice is: take both books and keep studying by them. I've learned Theoretical Computer Science by the Lewis & Papadimitriou book, but always I couldn't get a concept, I went to Sipser. And vice-versa.
At last, the 2012 (3rd) edition of the Sipser is so beautiful, with good automata drawings to understand Pushdown Automata. :)
From deleted twitter account
Dr_Craig_Wright twitted at 2015-05-10 02:06:51.000:
For those who wonder just how far you can "push" the scripting language in Bitcoin... http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Well, canon would be Garey & Johnson, but it's a bit behind the times. Arora & Barak as /u/DarkSayed suggests, Papadimitriou, and Sipser are all good alternatives.
> I want to be able to create functional programs with a bucket transistors, a cup of magnets, pen, and paper
I've heard good things about nand2tetris which goes from logic gates to a complete system with simple assembler, compiler and OS.
One good exercise might be to create an emulator for a simple system, like CHIP-8 or DCPU-16.
If you want to go deeper:
Introduction to the Theory of Computation by Michael Sipser: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Edit: wow, that book is more expensive than I remember. I have the 2nd edition, which can be found for a fraction of the price of the latest new edition. I'm not sure how they compare in content, though.
You'd like this book a lot.
Another one that's more hardcore EE than computer science is The Mathematical Theory of Communication. Shannon's 1948 paper this book highlights is the foundation of information theory.
Start with getting the XCode developer tools and the command-line package.
C is an important language in Computer Science because it is pretty much the language for heavy duty Operating Systems, the type you see in Desktop OSes, Network OSes (the type that runs on a networking router/switch), Server OSes (Linux, BSD, Windows, etc.).
I think C is a hard language to learn, but it is a great first serious language while also simultaneously learning an easier language like shell or Python to make yourself more efficient/productive.
However fundamental to CS is about the theory of comptuation not really languages. Languages are just a way to express computation. Some languages are better than others for expressing computation to solve certain problems. I would highly encourage also looking into understanding computation from first principles, a great introduction is Theory of Computation (2nd edition is really really cheap used). The only background knowledge you need to know is highschool mathematics.
Can I say Sipser's Introduction to the Theory of Computation? I know there are issues people have with the book, but in terms of accessibility and ease of reading, I think this text is second to none. I mean, though it says in the preface it's designed for upper-level undergraduates or fresh grad students, it makes no assumptions on the reader's level of knowledge, and as such I would feel comfortable recommending it even to some high school students.
OK,
https://mitpress.mit.edu/books/introduction-algorithms
get an old version: https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
try out hackerrank challenges
Then you could take Linear Algebra, Real Analysis or Abstract Algebra.
Or you could read books like Introduction to the Theory of Computation by Michael Sipser
>If you want to go more theoretical, look into set theory, regular languages, automata and state machines.
Sipser covers these with a theoretical-leaning book: https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Oh my god you're a fucking moron. Did you even read my comment? If you are discussing theory and this is your reply to my comment, you have a fundamental misunderstanding of the theory. The other explanation is you read something incorrectly, which wouldn't be such a problem but then you adopt such a cunt tone in your reply.
In theory
>Anything that can be done with a regex can be done with a finite automaton, and vice versa
Where did I state that recognising an email is impossible with finite automata? If something can be recognised by a finite automaton, it can be done with a regex.
Your original comment said that you cannot do this with regex but can with finite automata, but in theory
>They are equivalent in their expressive power, they both recognise the set of regular languages.
Anybody who has a semblance of an idea of what they're talking about will agree that they are in theory equivalent. So you can do it with regex, in theory.
Your article that you linked but didn't read carefully, states this same fact.
>And can you fully implement the complex grammars in the RFCs in your regex parser in a readable way?
It talks about the practical issues, e.g. being able to do it in a readable way with regex, because in fucking theory they are equivalent in their expressive power.
You may find the below useful:
https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Alternatively:
https://www.amazon.com/gp/product/B00DKA3S6A/ref=s9_acsd_top_hd_bw_b292I_c_x_5_w?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=merchandised-search-3&pf_rd_r=DQJA7YYF6XRPQ9DCCW1S&pf_rd_t=101&pf_rd_p=b949820f-ff03-5be8-b745-f0a5e56b98c9&pf_rd_i=511394
https://www.amazon.com/gp/product/B001E95R3G/ref=s9_acsd_top_hd_bw_bFfLP_c_x_1_w?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=merchandised-search-4&pf_rd_r=MXQ2SVBM01QEAAET2X18&pf_rd_t=101&pf_rd_p=c842552a-f9c9-5abd-8c7d-f1340c84cb6d&pf_rd_i=3733851