The full text of Boaz Barak's book "Introduction to Theoretical Computer Science" is available online for free, with the coveat that it's a "work in progress". The book centers on the universality of many different computational models, the related notion of the duality between code and data, and the idea that one can precisely define a mathematical model of computation, and then use that to prove (or sometimes only conjecture) lower bounds and impossibility results. The book starts by showing how grade-school multiplication is more efficient that just repeatedly adding, then how there is an even more efficient algorithm known as Karatsuba's algorithm, which came about because Anatoly Karatsuba was attending a lecture by Andrey Kolmogorov in 1960, in which Kolmogorov speculated that a more efficient algorithm was not possible and Karatsuba took on the challenge. Karatsuba's algorithm might be a challenge for you to remember, though, as, unlike the grade-school algorithm, it is recursive -- not a problem for a computer, though. The book goes on to prove the algorithm works mathematically, setting the tone for the rest of the book -- everything is mathematically proven.

If you've ever heard of such things as NP-completeness, the power of randomness on one hand and the possibility of derandomization on the other, the ability to use "hardness" for cryptography, and the possibility of quantum computing, this book works them out theoretically proof by proof.

Topics covered in the book include sets, functions, graphs, data representations, countable sets and Cantor's theorem, boolean circuits,NAND circuits and their universality (with mathematical proofs), Turing machines, the Church-Turing thesis, the equivalence of Turing machines and NAND-TM programs, the computability of functions, automata and cellular automata, regular expressions, lambda-calculus and functional programming languages, the uncomputability of the halting problem, restricted computational models to bypass limitations such as uncomputability of the Halting problem and Rice's Theorem (proof of the undecidability of whether programs have a given property), connection between uncomputability and unprovability (of theorems) (verification algorithms), context-free grammars, Diophantine equations and the MRDP theorem (theorem that computably enumerable sets are Diophantine), the efficiency of algorithms and big-O notation, the satisfiability problem, quadratic equations, matrix computations, running time, non-uniform computation cost, polynomial time reduction, reasoning about "hardness" (no, not talking about diamonds -- "hardness" here refers to the difficulty of computation), completeness, NP completeness, the Cook-Levin Theorem, randomized computation, cryptography, and quantum computing.

Introduction to Theoretical Computer Science

#solidstatelife #mathematics #computerscience