N or Space for next slide, P for previous slide, F for full screen, M for menu

Lec 7: Equivalent models

Boaz Barak (instructor), Brian Sapozhnikov (Head TF), Albert Chalom, Alexis Ross, Charles O’Mara, Daniel Chen, David Li , Jambay Kinley, Jane Ahn, John Shen, Josh Seides, Laura Pierson, Pranay Tankala, Raymond Lin, Theresa Nguyen, Wanqian Yang, William Fu, Hikari Sorensen (Extension TF), Eric Lu (Patel Fellow)

Laptops/phones only on last 5 rows please.

Find this course fast?

Good time to rejoin material.

Focus on the important points - see top 10 theorems

Ask questions when you read.

Focus on statements rather than proofs

Make sure you understand the question before thinking of the answer.

Understand quantified statements - game between you and adversary

Go to sections!

\(\lambda\) calculus won’t be on midterm.

Contact Patel fellow Eric Lu ericlu01@g.harvard.edu

Computational models

NAND++ / Turing Machines / NAND<< / \(\lambda\) calculus/…: Everything you can do in 〈your favorite language〉

NAND / Boolean circuits / ANDORNOT / …: Everything you can do in 〈your favorite language〉 for \(n\) input bits, unrolling all loops.

CS 121 Top 10 theorems

Finite computation

Thm 1: “Equivalence of universal bases” NAND programs \(\equiv\) NAND circuits \(\equiv\) AND/OR/NOT circuits \(\equiv\) \(\mathscr{U}\)-circuits, for any universal \(\mathscr{U}\).

Thm 2: “Universality of NAND” Every function \(F:\{0,1\}^n \rightarrow \{0,1\}\) has a NAND program of \(O(2^n/n)\) lines.

Thm 3: “Counting lower bound” Some (in fact most) functions require \(\Omega(2^n/n)\) lines.

Thm 4: “If it’s finite and you can Python it, you can NAND it” NAND \(\cong\) NAND + sugar

Thm 5: “Universal Circuit” Evaluate \(P,x \mapsto P(x)\) in \(poly(|P|)\) gates.

Arbitrary length computation

Thm 6: “unrolling the loop” If \(F\) is computable by NAND++, restriction of \(F\) to \(\{0,1\}^n\) is computable by NAND with similar resources.

Thm 7: “Turing completeness” NAND++ = Turing machines = NAND<< = RAM machines = \(\lambda\) calculus = Python = cellular automata = …

Thm 8: “Universality” \(EVAL\) for TM/NAND++/\(\lambda\)/Python… is computable by TM/NAND++/\(\lambda\)/Python…

Next up:

Thm 9: “Uncomputablity” NAND++ \(\neq\) Everything.

Thm 10: “Halting and friends” There are interesting uncomputable functions.

Today’s Theorems

Thm 7: “Turing completeness” NAND++ = NAND<< = \(\lambda\) calculus

Thm 8 ⃰: “Universality” There is a NAND<< (hence NAND++) program to compute \(P,x \mapsto P(x)\) where \(P\) is NAND++ (hence NAND<< ).

Today’s Message

“Have the cake and eat it too” paradigm: Move between levels of abstractions and equivalent models.

Last week: NAND++ and Turing machines

Local storage - states (Turing machines) or scalar variables and current line (NAND++).
Unbounded size memory - tape (Turing machines) or array variables (NAND++)

Sequential access - head location (Turing machine) or index variable i moves one step at a time.

Random Access Memory (RAM)

Can access arbitrary memory location at each step.

In C: foo = *bar or foo = Array[bar]
In Python: foo = Array[bar]
In NAND<< : foo = Array[bar]

NAND<<

Integer valued variables: arithmetic operations.
Indirect indexing: Bar[foo] is foo-th location at Bar

Trivial: If \(F\) is computable by NAND++ then \(F\) is computable by NAND<<

Harder: If \(F\) is computable by NAND<< then \(F\) is computable by NAND++

Exercise: Write NAND++ code to implement foo = Data[Index] where Data and Index are arrays and foo is scalar variable. Can use GOTO, inner loops, and i += var, i -= var sugar.

NAND<<

Integer valued variables: arithmetic operations.
Indirect indexing: Bar[foo] is foo-th location at Bar

Trivial: If \(F\) is computable by NAND++ then \(F\) is computable by NAND<<

Harder: If \(F\) is computable by NAND<< then \(F\) is computable by NAND++

Exercise: Write NAND++ code to implement foo = Data[Index] where Data and Index are arrays and foo is scalar variable. Can use GOTO, inner loops, recursion, and i += var, i -= var sugar.

Solution


def LOOKUP(Table,Index):
    Temp = COPY(Index)
    while  not ZERO(Temp):
         i += 1
         DECREMENT(Temp)

    return Table[i]

From NAND<< to NAND++

Step 1: Replace arrays of integers with two dimensional arrays of bits Array[i][j] is j-th bit of Array[i]

Step 2: Replace arithmetic operations with implementations - “syntactic sugar”

Step 3: Replace two dimensional arrays with one dimensional ones Array[i][j] becomes Array[pair(i,j)] \(pair:\mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}\) is computable and one to one.

Step 4: Replace indirection with lookup code: foo = Data[Index] becomes foo = EXERCISE(Data,Index). All arrays now indexed with i using i += blah , i -= blah

Step 5: Replace while with GOTO, replace GOTO with if (linetorun == thisline) { do something }, implement if via syntactic sugar.