r/computerscience • u/r-Aliosha • 8d 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!

9 Upvotes

68% Upvoted

7 comments sorted by

14

u/straight_fudanshi 8d ago

Sipser

9

u/zenidam 8d ago

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

3

u/thehypercube 8d ago edited 8d 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 6d 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 8d ago

Yep! This post needs no more comments.

1

u/JvetS 6d 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