boazbk / tcs Goto Github PK

RHS of the inequality should have |E(o)| rather than |o|

p.175 // finishedloop is initalized to 0 —> // finishedloop is initialized to 0

It is not clear to me how
while (a) {
loop_code
}
is equivalent to
if NOT(finishedloop) {
if (a) {
code2
}
if NOT(a) {
finishedloop := 1
}
}
Is there an implied condition to repeat the if NOT(finishedloop) {…} block?
At p.173, the implied condition for repeating the execution is that the loop variable equals 1, but here?

p.179 array of bits(which we have —> array of bits (which we have

p.180 contains an OCaml program that transform —> contains an OCaml program that transforms

p.184 etc.. --> etc.

p.184 Before we prove Theorem 12.2 formal --> Before we prove Theorem 12.2 formally

some points that would be good to add to this section:

• consequently, the classes P and EXP are robust to the choice of model (provided the model satisfies the ECTT)
• thus we can use high-level descriptions of algorithms, like those given in chapter 13, to determine whether a problem is in P
• P and EXP are also robust to most encoding of inputs (because poly(poly(n)) is also poly(n)), however note the difference between binary and unary inputs (the latter being "pseudopolynomial").

"b that correspond to a" -> "b that corresponds to a"

the bullets with the example of well-formed arithmetic expressions:

• the operation variable is not used
• a Rightarrow is missing a \
• there are a couple of "(expression"s on the LHS of rules
  it would be more readable if every rule were a separate line (using two columns to save space)

the text before thm 11.2 talks about functions halting rather than programs, whereas earlier we have stressed that functions are not the same thing as programs

When discussing the simulation of lambda calculus by TMs, something nontrivial that needs to happen is parsing of the lambda expression, which is needed in order to figure out how to search and replace. Also it's important to use a reduction rule that is guaranteed to halt.

p.67 thrity-nine —> thirty-nine

p.70 x+x′( modb) —> x+x′(modb)

p.71 // add least signifcant digits —> // add least significant digits

p.74 that uses the these features —> that uses these features

p.74 an equivalent program that does not use it —> an equivalent program that does not use them

p.79 If at tbe ith stage —> If at the ith stage

p.82 outputting LOOKUP(a, b, i_{k−1}). —> outputting LOOKUP_1(a, b, i_{k−1}).

p.83 see ??.

p.83 a table of the its values —> a table of its values

p.83 Note 11 overlaps with G(x) = LOOKUP_4(1100100100001111, x).

p.87 the list of exercises starts with Exercise 3.7 rather than 3.1

worth saying/repeating what the continuum hypothesis is here.

missing comma after <

I'd also suggest allowing "->" as one of the logical operations, as it can make the examples below much more readable

it'd be nice to start by illustrating recursion with the concrete example of parity (or some other recursive function), and showing how it computes on a particular input, and then generalize to the abstract Y combinator construction.

before Thm 10.3: might be nice to replace "confirm with some specification" with something specific, eg correctly computing integer multiplication, or never writing to certain "dangerous" memory locations. (such things can provide good exercises on undecidability)

worth mentioning that the by the Church-Turing thesis, the use of NAND++ programs here captures all reasonable algorithmic methods for proof verification.

also the lowercase p in the last sentence of the def should be capitalized

p.106 the only way perform computation. —> the only way to perform computation.

p.109 Figure 5.6: Implementing a NAND gate using transistors —> Figure 5.6: Implementing a NAND gate using transistors.

p.108-110 The informal definition of Boolean circuits is a bit confused, imo.
The first statement focuses on circuits based on gates that map k bits to 1 bit.
Then the definition changes its focus to functions with n input bits and m output bits (“We have n special wires..”). I think a link is missing, between the first and second part of the definition.
p.s. The formal definition is clear.

p.110 There should be exactly m sink vertices and every one of them gets a unique label —> There should be exactly m sink vertices and every one of them gets a unique label.

p.114 s lists of K numbers —> s lists of k numbers

p.114 to be the function to be the function that takes —> to be the function that takes

p.115 Then the PCETT would imply —> Then the PECTT would imply

p.116 .. = 20.8104 NAND lines —> add a \cdot between 0.8 and 10^4 in the exponent
p.116 same as above: 20.2104−360
p.116 same as above: 20.2104−150

p.116 in Note 7: we can get aroudn this issue —> we can get around this issue

p.116 5.8.1 Attempts at refuting the PECTT: —> 5.8.1 Attempts at refuting the PECTT

p.116 that cannot be done b y —> that cannot be done by

p.117 suoptimal results —> suboptimal results

p.118 open questionIn fact, —> open question. In fact,

p.218 it is enough to show give a Turing machine —> it is enough to give a Turing machine
p.221 We can use this approach, to achieve —> We can use this approach to achieve
p.222 note 9 is missing
p.228 in eq. (9.8) and (9.10): otherwise is attached to the formula, should be mved to the right

(I paused to attend QCrypt and WQRN, but now I am back :)

"humanity...that she cared" -> "humanity...that it cared"

In the advanced note:-

line 15 - need to add a right bracket at the end of the line
line 17 - the x subscript n-k should be n-k-1
line 22 - "by" should be "be"

Re the box on recursion in NAND<<: Students reading this may have never seen stacks and how recursion is actually implemented using them, so this may be cryptic to them. Here one should talk about how the local variables, current line number, and input vars are pushed on to the top of the stack, the line counter is changed to the start of the recursively called routine, and then what that routine finishes, we pop those things off in order to continue the computation with the configuration updated according to the output.

The first sentence can begin "As we saw in Chapter 9,"

pg 200. middle: "such as i++ (foo) and i- (bar)" -> "such as i++ (foo) and i-- (bar)"
pg 200. at bottom: "attstart" -> "atstart"

pg 201. The definition of PAIR is missing a "+x" at the end (otherwise it is certainly not one-to-one and confusing until one reaches exercise 8.1)

pg 205. 8.3.1 "Theorem 14.2" -> "Theorem 8.2"

In the clean proof for "Every connected undirected graph of 𝑛n vertices has at least 𝑛−1n−1 edges", I beleive there is a typo in this paragraph:

On the second line should this read a graph of k edges? Because otherwise it would be self evident that any vertex in a graph with k vertices would have fewer than k + 1 connected vertices.

Note I am reading from the website so this may be different from what is in the repository.

• Hamish Nicholson

I believe there is a small typo on page 102, definition 3.1. Should it say "Intuitively, the l-th element..." rather than "Intuitively, the l-the element.." on the second line in the screenshot?

Hi,
I found the following typos in Chapter 1:

p.40 that can allow us to compute and these data —> that can allow us to compute these data
p.41 data structures and algorithm are useful —> data structures and algorithms are useful
p.43 the formula for summing a gemoetric series. —> the formula for summing a geometric series.
p.46 many “reasonable” approache for computing —> many “reasonable” approaches for computing
p.46 Archimedes one said —> Archimedes once said
p.47 1.023Mhz —> 1.023MHz

first paragraph "sill complete" -> "will complete"

in the discussion of execution traces, it may be confusing to have different meanings for $i$ and $\texttt{i}$

change

By rounding up $st$ to the nearest power of $2$ (which at most doubles its size), we can assume the array avars is of length $2^k$ for $k=\lceil st \rceil$.

to

By rounding up $st$ to the nearest power of $2$ (which at most doubles its size), we can assume the array avars is of length $2^k$ for $k=log (\lceil st \rceil$).

add log function to st.

For Theorem 3.5 (p. 107), it mentions a function "H". Would this possibly be referring to a different function, as I don't see H being defined anywhere prior?

would be helpful to add a few sentences about what a "queue" is and what push and pop mean

"The output is the value of the variables y_0, ……, y_⟨𝑚−1⟩⟨m−1⟩. (If a variable of the form y_⟨𝑖⟩⟨i⟩ has not been assigned a value in the program, then its value defaults to 00.)"

The bit in parentheses is inconsistent with needing every output variable to appear in the program.

Sarah Turnill

some more help in how to interpret and apply the pumping lemma as in Sipser would be helpful, eg around the alternation of quantifiers, the fact that it is a necessary but not sufficient condition for regularity, etc.

for each of the following two functions, say whether it is decidable (computable) or not:

1. Given a NAND++ program P, an input x, and a number k, when we run P on x, does the index variable ever reach k?
2. Given a NAND++ program P, an input x, and a number k, when we run P on x, does P every write to an array at index k?

there are extra spaces appearing in the formatting of "i--"

One possibility is to follow our intuition above that with a budget of k edges, we cannot connect to a vertex more than k−1 other vertices.

k-1 should be k.

Prove that $|A_1 \cup \cdots \cup A_k|
should be
Prove that $|A_0 \cup \cdots \cup A_k-1|

p.93 we will spell out precisely how represent NAND programs —> we will spell out precisely how to represent NAND programs

p.95 Note 4: to maintain compatiblity —> to maintain compatibility

p.97 Note 7: we can find a NAND program for the function restricted to n inputs will have —> we can find a NAND program for the function restricted to n inputs that will have
(I am not 100% sure the original statement was wrong, but this other version sounds better to me)

p.98 Note 8: RISC in turn stands for “Reduced instruction set computing” —> RISC in turn stands for “Reduced instruction set computer”

p.98 such as the LEG acrhitecture —> such as the LEG architecture

p.98 to convert a Pyyhon program —> to convert a Python program

p.99 Counting programs, and lower bounds on the size of NAND programs. —> Counting programs, and lower bounds on the size of NAND programs

p.99 the implicit constant in the O(·) notation in Theorem 4.3 at most 10. —> the implicit constant in the O(·) notation in Theorem 4.3 is at most 10.

p.101 We can even write a NAND programs —> We can even write a NAND program

p.101 etc.. —> etc.

p.101 Exercises start from 4.5 rather than 4.1

p.102 when all its input are —> when all its inputs are

p.102 Note 9: Hint: Show that that the array avars will alwaus —> Hint: Show that the array avars will always

p.102 At the moment, the best we unconditional lower bound known —> At the moment, the best unconditional lower bound we know

before proving the undecidability of the halting problem, it may be worth discussing how to design a decider for it. One idea is to use the universal NAND++ program, and then discuss why it doesn't work. (Can also point out the distinction between easy-to-identify infinite loops, where a configuration repeats, and the more general kind of "infinite loop" where the program keeps running forever but never repeats a config. actually I guess with the INDEX schedule in NAND++, configurations never repeat. but there can be with NAND<< or other programming languages.)

lec 03 says

As mentioned in the appendix, we require that all output variables are assigned a value, and that the largest index used in an 𝐿 line NAND program is smaller than 𝐿, and so all functions in 𝑆𝐼𝑍𝐸(𝐿) have at most 𝐿 inputs and 𝐿 outputs.

but appendix says

If the variable identifiers are indexed, the index can never be larger than the number of lines in the program.

so in order to make this single line program "y_0 := x_0 NAND x_1" valid

"the largest index used in an 𝐿 line NAND program is smaller than 𝐿"
should be changed to
"the largest index used in an 𝐿 line NAND program is smaller than or equal to 𝐿"

and for the same reason ,in lec05 we should change

Of course this limitation is inherent for the NAND programming language where an 𝑁-line program can never compute a function with more than 𝑁 inputs.

to

with more than 2*𝑁 inputs.

it'd be helpful to start with more concrete examples of the lambda calculus and its evaluation, maybe where we allow integer constants and arithmetic operations, e.g. \lambda.x (x^2+2x+3) and something similar for functions of two variables. Seeing lambda.x e and e[x->y] is way too abstract to get one's head around.

after that, it seems good to give an actual inductive definition of the syntax and semantics of this sugared lambda calculus and state the Church-Rosser theorem that any halting sequence of reductions will yield the same result (commenting on the nondeterminism here may be valuable).

implicitly this proof depends on the fact that the partition of exp into subexpressions is unique. this is due to the unambiguity of the grammar defining regular expressions when you write it with all the parentheses. without all the parentheses, then there is ambiguity - and one needs to confirm that it doesn't matter how you parse it. For example exp'exp''exp''' can be parsed two ways, but it doesn't matter due to associativity of concatenation of languages.

The side note says "that there is way to "count" all the reals as NtR(0), NtR(1),...".

I believe that it should say "that there is NOT a way to "count" ...".

Thanks!

after thm 10.1, the book says the proof uses in an essential way the view of a program as a string that can be input to computation. that's not true for thm 10.1 - we only need the set of programs to be countable, not that there is any effective encoding of them. thm 10.2 (undecidability of the halting problem) does use that view in an essential way, indeed even for the statement of the thm.

also, it would be nice to convey the counting argument proof of thm 10.1, which draws a nice parallel to what was done for NAND programs

def c := AND(a,b) {
notc := a NAND b
c := notc NAND c
}

c := notc NAND c should be c := notc NAND notc

----> "S = {s_0, s_1,...s_{m-1}}" : since k = |S|, I think it should be: "S = {s_0, s_1,...s_{k-1}}"

----> "If t_j was marked before them we have found" : I think it should be: "If t_j was marked before, then we have found"

----> "in this case E(m) must map" : I think it should be: "in this case E(s_m) must map" (because I'm not sure what E(m) would refer to)

p.190 in most textbook —> in most textbooks
p.190 the Engima cipher —> the Enigma cipher
p.191 has access to an tape —> has access to a tape
p.193 In addition to the standard syntactic sugar, we assumed above —> In addition to the standard syntactic sugar we assumed above,
p.196 memory. the state accordingly —> ?
p.198 etc.. —> etc.
p.199 via replacing all copies of the x parameter with x). —> via replacing all copies of the x parameter with z).
p.202 a single REDUCE operations. —> a single REDUCE operation.
p.204-205 there are references to Eq. (8.13) which has never been stated yet; I think the correct reference is Eq. (8.7)
p.205 direction of ?? —> direction of Theorem 8.2
p.206 Chapter 8 of the book The Nature of Computation is wonderful resource —> Chapter 8 of the book The Nature of Computation is a wonderful resource
p.207 its 8 vertical, horizontal and vertical neighbors. —> its 8 vertical, horizontal and diagonal neighbors.
p.208 The Wikipedia page for the Game of Life contain —> The Wikipedia page for the Game of Life contains
p.210 Alice and Bob might pool their funds together sign a contract to create a joint venture —> Alice and Bob might pool their funds together, sign a contract to create a joint venture

Hi Boaz,

I just wanted to let you know about some typos in lecture notes and problem set 1:

• Figure 3.6 in notes (gradschool --> grade-school)
• 4.1: Two periods in section
• 4.1.1: We can create variables zero and one that are have
  4.1.6 Footnote formatting at the end.
  Problem Set 1: Problem 2.1: The problem statement and the "In other words" aren't saying the same thing logically. It's not hard to see that the "in other words" is a stronger statement, but it would be nice if "in other words" actually meant they were equivalent.

"a multivariate polynomial with integer coefficients P: R^k->R" -> "a multivariate polynomial P(x_1,...,x_k) with integer coefficients". I'd use x_i's for variables and something else for values to plug in.

p.51 (caption of Fig. 2.1) some process that maps and input to an output —> some process that maps an input to an output

p.53 the decoding function is defined as D(x_0,..,x_{n-1}) = 2^0 x_0 + .. + 2^{n-1} x_{n-1}, but should be D(x_0,..,x_n) = 2^0 x_0 + .. + 2^n x_n, according to previous definitions

p.53 note 4: why using the empty string (length zero) for representing 0, rather than 00..0?

p.54 ..with the binary representation of k). —> with the binary representation of k.

p.54 .. is prefix free if for there are —> if there are

p.56 but in many (thuogh not all) —> but in many (though not all)

p.56 this does not effect the final result —> this does not affect the final result

p.56 2.1.1 Representing lists: —> 2.1.1 Representing lists

p.58 Reimann Hypothesis —> Riemann Hypothesis

p.59 etc.. etc.. —> etc. etc. (also at the bottom of the page)

p.59 an prohibitively large amount —> a prohibitively large amount

p.59 Can a function being hard to compute every be a good thing? —> Can a function being hard to compute be a good thing?

p.59 x might be description of a set of equations —> x might be the description of a set of equations
and R(x) will be the set of all solution —> and R(x) will be the set of all solutions

p.61 check the definition of reverse binary representation: I think i=0,..,n-1 should be i=0,..,k instead

p.61 If x, y are number between —> If x, y are numbers between

p.62 Exercise 2.5: “prefix free” is used, instead of “prefix-free” which is used all throughout the chapter

p.63 real numbers as stings —> real numbers as strings

p.63 Exercise 2.8: item c. is included in item b.; similarly, items e. and f. are included in item d. (but maybe this is deliberate..)

p.63 arrived at more rigorous notion —> arrived at the more rigorous notion

Shouldn't the second o_i be prime? It's a small typo, but just thought I would point it out. In addition, should the k at the end be k'?

In addition, I might be wrong but thought that this j was supposed to be i, keeping in line with previously defined notation:

Thank you!

On the third line of the definition, I believe that it should say $l \in [s]$, instead of s+1. The line above defines s as |L|; however, [s+1] = {0,...,s}, which is |L|+1.

after the def of Phi_exp, it'd be good to illustrate with examples of how various strings match the regexp of (11.2)

Hi,
First, whoo 👏 bravo for this work, it might be a work in progress but it is already quite complete and impressive. Well done! Keep doing that!

Second, I tried to access the website with different browsers, and apparently MathJax is not loaded correctly.
I see that you are using a cloudfront CDN, but even if cdn.mathjax.org is dead now, the official suggested CDN is https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js.

Also, I don't know how do you compile the PDF book and the website, and maybe it could be useful to also open-source the build script, if that doesn't bother you?
Ideally, for such projects, I think anyone could download the zip archive, rebuild the PDF with something as simple as "make pdf", et voilà. For instance, we have tried that for @LaurentClaessens's mazhe.

Thanks in advance.