N or Space for next slide, P for previous slide, F for full screen, M for menu
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
Slides will be posted online.
Laptops/phones only on last 3 rows please.
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?
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
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}\).
NAND + LOOPS + Indexing = NAND++
If \(P\) is a NAND++ program, to execute \(P\) on \(x\in \{0,1\}^*\):
For \(T=1,2,3,\ldots\) do:
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.
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
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\).
What is computation? Local evolution of global state according to a finite set of instructions.
DNA, physical systems, bee colonies, slime mould, markets..
Three types of memory access: