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

Lec 8: NAND++

Boaz Barak (instructor), Salil Vadhan (co-instructor), Juan Perdomo (Head TF).

Team: Aditya Mahadevan, Brian Sapozhnikov (surveys), Chan Kang (extension), Gabe Abrams (Ed Tech), Gabe Montague (NAND web), Jessica Zhu (proof workshops), John Shen, Juan Esteller (NAND implementation), Karl Otness, Katherine Binney, Lisa Lu, Mark Goldstein (clicker expert), Stefan Spataru, Susan Xu, Tara Sowrirajan, Thomas Orton (Advanced Section), Wentong Zhang

http://tiny.cc/cs121

Slides will be posted online.


Laptops/phones only on last 3 rows please.

Infinite functions

Up till now: Talked about finite functions \(F:\{0,1\}^n \rightarrow \{0,1\}^m\)

Today: First introduction to infinite functions \(F:\{0,1\}^* \rightarrow \{0,1\}^*\)

Or is it?

NAND++

Which of the following functions is computable by a NAND++ program?

a. \(ADD(a,b) = a + b\).

b. \(MULTIPLY(a,b) = a \cdot b\)

c. \(LOG(a,b) = \max \{c \in \mathbb{N}: b^c \leq a \}\).

d. All of the above

Why NAND++?

Goal: Compute infinite function \(F:\{0,1\}^* \rightarrow \{0,1\}\) with finite set of instructions.

Need to handle \(\text{Input length} \gg \text{Program length}\).

  • Repeat same instructions many times. Loops!
  • Allow access to memory \(\gg\) program length. Arrays!

NAND + LOOPS + Indexing = NAND++

NAND++ view 1

NAND++ view 2

If \(P\) is a NAND++ program, to execute \(P\) on \(x\in \{0,1\}^*\):

For \(T=1,2,3,\ldots\) do:

  • \(P^T\) = NAND program \(P_0 P_1 \cdots P_{T-1}\)
    (\(P_\ell\) copy of \(P\) with “search and replace” \(i \leftarrow INDEX(\ell)\).)
  • Run \(P^T(x)\). If loop gets value \(0\) then break out of loop.

What is a constant?

The program size, number of variables, length of block of configuration are fixed in advance. (before we get the input)

The number of iterations, position of index variable, number of blocks, length of configuration all depend on the input length. (grow with the input length)

The point of NAND++: A constant sized recipe how to execute an unbounded in advance number of operations.

Configurations

A configuration of \(P\) at step \(\ell\) encodes all the state at given point: Boolean variables, index variable, current line

Encoded as \(\sigma \in \{0,1\}^{Br}\)

\(B\): constant \(\color{gray}{(B=2(5+t+\log(\lceil s+1 \rceil))}\)
\(r-1\) largest index with nonzero var.

Format: \(i\)-th block is \(\mathtt{BB}\; var^0_i \; var^1_i \; \ldots \; var^{t-1}_i \;\; start \; final \; active \; p \;\; \mathtt{EE}\)

Default indices: \(x\):0, \(y\):1, \(validx\):2, \(loop\):3, \(halted\):4, \(indexincreasing\):5

Exercise

Consider a programming language STRINGS with no loops but only the following operations:

  • No variables. Input is binary string s and s is also the output.

  • replace(s,pattern1,pattern2) replaces the first occurrence of literal pattern1 in s with pattern2.

  • if search(s,pattern) then { code } performs code if pattern is a substring of s.

Prove in groups: For every \(s\)-line NAND++ program \(P\) There is a STRINGS program of at most \(2^{100 s^2}\) lines that computes \(NEXT_P\).

Proof

High level takeaway

What is computation? Local evolution of global state according to a finite set of instructions.

DNA, physical systems, bee colonies, slime mould, markets..

Syntactic sugar: \(i++\) and \(i--\)

Three types of memory access:

  • Oblivious: Topology is fixed in advance independent of input. (NAND, Hardware, Internet,..)
  • Sequential: Memory is one dimensional array, can travel on it one step at a time. (\(i++/i--\) sugar, Turing machines)
  • Random access: Memory is array/dictionary, can access memory at any address at unit cost. (RAM machines, programming languages)

Syntactic sugar: \(i++\) and \(i--\)

NAND++ to NAND

Opps, you cannot play draw N guess with this browser!