r/computerscience • u/r-Aliosha • 14d ago

Help Libros de Teoria de la Computación

Buenas! soy estudiante de matemática, quería preguntar si alguien conoce buenos libros de teoría de computación, pero más orientado a fundamentos de las matemáticas que a aplicaciones como tal. Maquinas de Turing, autómatas, todo eso.

Gracias!

10 Upvotes

67% Upvoted

8 comments sorted by

13

u/straight_fudanshi 14d ago

Sipser

9

u/zenidam 14d ago

I can't think of another subject where one textbook is so universally considered the clear winner.

3

u/thehypercube 14d ago edited 14d ago

It's not, very far from it. First of all, there are other books covering the same material and just as good or better as Sipser, e.g., Hopcroft & Ullman; John C. Martin's book is also pretty good, as is Moret's.

Then for classical computability/recursion theory (e.g., Kleene's recursion theorem, mu-recursive functions) you can't go wrong with Cutland, whereas Garey & Johnson present the most readable proof of the Cook/Levin theory and the theory of NP/completeness.

All of these books give only a very rudimentary introduction to complexity theory. To go into depth, Arora and Barak is good and comprehensive, if a bit terse at times; Moore & Mertens covers less material but is a joy to read.

Finally, there are some books covering the connections between computability theory and first order logic, Gödel's completeness and incompleteness theorems, skolemization, etc. Boolos, Burgess, and Jeffrey is a good read for this.

2

u/straight_fudanshi 12d ago

Thanks for the recommendations. I used Sipser and Hopcroft for my TC course. I just really like how easy Sipser's is to follow. Will definitely check your other recs before I start my masters :)

0

u/Black_Bird00500 14d ago

Yep! This post needs no more comments.

1

u/JvetS 12d ago

It’s not exactly what you’re asking for, but you might find Knuth’s The Art of Computer Programming enjoyable.
The collection is an admirable body of work regardless of whether it scratches that math itch for you.
I have an edition from 10+ years ago and it’s one of my favorite sets even though a lot of chapters are irrelevant to my day job and challenging to fully grasp at first.

https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

1

u/jepstream 1d ago edited 1d ago

---Algebraic Theory of Machines, Languages, and Semigroups - Michael Arbib (Arbib is a good reference in general)

---Automata, Languages, and Machines - Samuel Eilenberg (yes, that one)

---Introduction to Mathematical Logic - Alonzo Church (covers multi-valent propositional logic well, also contains important references, in my opinion is a better alternative to Enderton)

---Theory of Recursive Functions and Effective Computability - Hartley Rogers Jr. (another classic reference)

Also, if you really like "Abstract Algebra" and computation theory then you need to learn semigroups and free monoids. Krohn-Rhodes decomposition, words, trees, etc.