Chapter 3, Defining Computation

[michelle-chiang]

Chapter name: Chapter 3, Defining computation

List of bugs/typos 1 From the text:

𝑁𝑂𝑇 ∶ {0, 1} → {0, 1} defind as 𝑁𝑂𝑇 (𝑎) = 1 − 𝑎.

Suggested fix:

𝑁𝑂𝑇 ∶ {0, 1} → {0, 1} defined as 𝑁𝑂𝑇 (𝑎) = 1 − 𝑎.

2 From the text:

...for every 𝑛 using at most 4𝑛 basic steps involving applications of a function in {𝐴𝑁𝐷, 𝑂𝑅, 𝑁𝑂𝑇 } to omputs or previously computed values.

Suggested fix:

...for every 𝑛 using at most 4𝑛 basic steps involving applications of a function in {𝐴𝑁𝐷, 𝑂𝑅, 𝑁𝑂𝑇 } to outputs or previously computed values.

3 From the text:

Theorem 3.3 — NAND computes AND,OR,NOT.. We can compute 𝐴𝑁𝐷, 𝑂𝑅, and 𝑁𝑂𝑇 by composing only the 𝑁𝐴𝑁𝐷 function.

Suggested fix:

Theorem 3.3 — NAND computes AND, OR, NOT. We can compute 𝐴𝑁𝐷, 𝑂𝑅, and 𝑁𝑂𝑇 by composing only the 𝑁𝐴𝑁𝐷 function.

4 From the text:

If someone gave us a description of such an algorithm, could we use it to actually compute the function the real world?

Suggested fix:

If someone gave us a description of such an algorithm, could we use it to actually compute the function in the real world?

5 From the text:

We have already seen that allowing 𝐴𝑁𝐷,𝑂𝑅, 𝑁𝑂𝑇 as basic operations...

Suggested fix:

We have already seen that allowing 𝐴𝑁𝐷, 𝑂𝑅, 𝑁𝑂𝑇 as basic operations...

6 From the text:

...we can directly implement operations such as 𝑁𝐴𝑁𝐷, 𝐴𝑁𝐷, 𝑂𝑅, 𝑁𝑂𝑇 etc..

Suggested fix:

...we can directly implement operations such as 𝑁𝐴𝑁𝐷, 𝐴𝑁𝐷, 𝑂𝑅, 𝑁𝑂𝑇 etc.

7 From the text:

𝐴𝑁𝐷/𝑂𝑅/𝑁𝑂𝑇

Suggested fix (for consistency with rest of text):

𝐴𝑁𝐷, 𝑂𝑅, 𝑁𝑂𝑇

8 From the text:

3.3 FROM NAND TO INFINITY AND BEYOND..

Suggested fix:

3.3 FROM NAND TO INFINITY AND BEYOND...

9 From the text:

without going through the entire stack of architecture, operating systems, compilers, etc… as well as

Suggested fix:

without going through the entire stack of architecture, operating systems, compilers, etc. as well as

10 From the text:

This might seem as curiosity but there is a field known as fluidics...

Suggested fix:

This might seem merely a curiosity, but there is a field known as fluidics...

11 From the text:

...Conway’s “Game of Life” can be used to simulate computation gates, see Fig. 3.12.

Suggested fix:

Conway’s “Game of Life” can be used to simulate computation gates (see Fig. 3.12).

12 From the text:

For example, ine particular basis we can use are threshold gates.

Suggested fix:

For example, one particular basis we can use are threshold gates.

13 From the text:

...it seems that to a first approximation it can be modeled by a (very large) neural network.

Suggested fix:

...it seems that as a first approximation it can be modeled by a (very large) neural network.

14 From the text: Multiple occurrences of punctuation following a quotation mark; should be reversed.

Suggested fix: Example: Instead of "text", should be "text," .

15 From the text:

The NAND Programming Language

Suggested fix:

the NAND Programming Language

16 From the text:

The proof of Theorem 3.10 is constructive, in the sense that it yield an explicit transformation from a program to a circuit and vice versa.

Suggested fix:

The proof of Theorem 3.10 is constructive, in the sense that it yields an explicit transformation from a program to a circuit and vice versa.

17 From the text:

This turns out to be a special case of a general phenomena- the universality of 𝑁𝐴𝑁𝐷 and other gate sets- that we will explore more in depth later in this course.

Suggested fix (use em dash):

This turns out to be a special case of a general phenomena — the universality of 𝑁𝐴𝑁𝐷 and other gate sets — that we will explore more in depth later in this course.

[boazbk]

Thanks so much!

Fixed all except I didn't get to do a quotes/punctuation pass, but will try to do this at some point (I guess I'm adopting British conventions when it suits me ... https://www.quickanddirtytips.com/education/grammar/how-to-use-quotation-marks ) also need to make sure that any such change is not confusing.

You're right on almost all counts, though I think "to a first approximation" is standard usage ( https://www.webster-dictionary.org/definition/to%20a%20first%20approximation ) Tried to use unicode em dash - hopefully the markdown to pdf+html loop will handle this..

Feel free to do a pull request as well for fixes, though I'd be happy to get your input any way that's convenient for you!

Boaz

[singerng]

The definition of computing a function via a NAND program appears to be incomplete. Here's the relevant portion of the text:

Let F:{0,1}^n -> {0,1}^m be some function, and let P be a NAND program. We say that P computes the function F if:

1. P has n input variables X[0], ..., X[n-1] and m output variables Y[0], ..., Y[m-1].
2. For every x in {0,1}^n, if we execute P when we assign to X[0], ..., X[n-1] the values x0, ..., x{n-1}, then at the end of the execution, the output variables Y[0], ..., Y[m-1] have the values y0, ..., y{m-1}.

However, you never actually define the values y0, ..., y{m-1} relative to F, the function being computed.

Fix: Either write F(x)0, ..., F(x)_{m-1} instead of y0, ..., y{m-1}, or add an extra clause letting y = F(x).

[singerng]

Also, in the algorithm for computing increments, the number of steps is messed up; it appears as 1 2 1 2 1, whereas it should probably be 1 2 a b 3.

[ctduffy]

Hi, in the informal definition of the algorithm, there are two differing statements. The book first states that "An Algorithm is a set of instructions of how to compute an input from an output by following a sequence of 'elementary steps,'" and then goes on to say how we compute an output from an input with the elementary steps given in the algorithm. The issue here is that one way states that the algorithm goes from output to input, whereas the next says it goes from input to output. I think both should be input to output, but correct me if I am wrong/misunderstanding this.

[boazbk]

@ctduffy you are correct - an algorithm computes an output from an input and not the other way around @singerng will comment in the issue you opened