Computability, complexity, and languages
by Davis, Martin · first published 1983
2mentions
1recommended by
2HN commenters
2011–2016first – last mentioned
50% recommend50% neutral
This introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes very little background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
…(http://www.amazon.com/Introduction-Algorithms-Second-Thomas-...) "The Art of Computer Programming" (http://www.amazon.com/s/ref=nb_sb_ss_i_6_31?url=search-alias...) ....to begin with. Then there are theoretical computer science books. I like the Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing) http://www.amazon.com/Computability-Complexity-Languages-Sec...
on “Ask HN: Best Book(s) to Learn CS Degree Take-aways?” ↗The S language is a theoretical programming language proposed by Martin Davids in his book Computability, Complexity and Languages. It is composed by labels, variables, and 4 basic instructions, and its used between many things, to prove that there are natural functions (F: N^n -> N) which can not be computed. Awesome! If you want…
on “Show HN: An encoding/decoding tool for Martin David's theoretical S language” ↗