tcs
tcs copied to clipboard
boazbk
Book in preparation: introduction to theoretical computer science
**Chapter name**: Equivalent models of computation (section: "Turing completeness and equivalence, a formal definition (optional)") **List of bugs/typos** 1. In the section titled "Turing completeness and equivalence, a formal definition...
**Chapter name**: Loops and infinity **List of bugs/typos** 1. In the online site version under the section titled "“GOTO” and inner loops" (specifically, the remark "GOTO's in programming languages"), there...
**Chapter name**: Functions with Infinite domains, Automata, and Regular expressions **List of bugs/typos** 1. In online TCS site under the section titled "Algorithms for matching regular expressions," beneath the first...
**Chapter name**: Code as data, data as code **List of bugs/typos** 1. In the first figure's caption under the section titled "Representing programs as strings," the figure has a label...
**Chapter name**: Syntactic sugar, and computing every function (section: "The LOOKUP function") **List of bugs/typos** 1. Formatting Bug: In the online TCS version (in the section titled "The LOOKUP function"),...
**Chapter name**: Computation and Representation **List of bugs/typos** 1. In section titled "Two’s complement representation (optional)", the LaTeX in the second paragraph written as `$ k + k’ { -2^n,,...
In the 2SAT section, the first sentence has a small typo in defining a k-CNF formula - it's just missing the word "if". I think the definition could also explicitly...
**Chapter name**: Modeling running time. **List of bugs/typos** 1. The section containing the typo is **Oblivious NAND-TM programs**. It is at the very end of the section, after the sentence...
**Chapter name**: Code as data, data as code **List of bugs/typos** 1. The typo is under section **A NAND interpreter in Python**, after the line "Accessing an element of the...
**Chapter name:** Computation and Representation **List of bugs/typos** 1. The last sentence in the description for figure 2.8 currently says $\bar{d}(x)(n(x))\neq StF(x)(x)$ but I believe it should be $\bar{d}(n(x))\neq StF(x)(n(x))$