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

Lec 7: Physical implementation, programs as circuits

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.

Today

Physical implementation of NAND
Programs as graphs
Physical Church-Turing Thesis
Collaboration policy, honor code

Question

Name your favorite “game of thrones” character:

a. Jon Snow

b. Tyrion Lannister

c. Cersei Lannister

d. Daenerys Targaryen (First of Her Name, The Unburnt, Queen of the Andals, the Rhoynar and the First Men, Queen of Meereen, Khaleesi of the Great Grass Sea, Protector of the Realm, Lady Regnant of the Seven Kingdoms, Breaker of Chains and Mother of Dragons)

What is CS 121 about?

Duality of code and data Feeding programs to other programs or themselves.
Universality One program can evaluate all others.
Completeness and Emergence/Phase transitions All sufficiently rich models are equivalent.
Uncomputability and intractability The dark side of completeness
Role of randomness in computation
Hardness as a resource derandomization, cryptography
Physical world as a computer (e.g., biological systems, social systems, quantum computers,..)

Course outline

Transistors

Moore’s law

Move to notebook

General Boolean Circuits

Def: If \(B = \{ b_0,\ldots, b_{t-1} \}\) set of finite Boolean functions, a \(B\) circuit is circuit where all gates are functions in \(B\).

Universal basis

Def 1: \(B\) is universal basis if for every finite function \(F:\{0,1\}^n \rightarrow \{0,1\}^m\), there is a \(B\) circuit computing \(F\).

Def 2: \(B\) is universal basis if there is a \(B\) circuit computing the function \(NAND:\{0,1\}^2 \rightarrow \{0,1\}\) where \(NAND(a,b)= 1-a\cdot b\).

Which definition is correct?

a Def 1

b Def 2

c Both

d Neither

Physical Church-Turing Thesis

Informal: Compute a function \(F\) using \(s\) “physical resources” \(\approx\) \(F\in Size(s)\).

Policies, Honor code

Why have policies?

My undergrad experience: Israeli/European system: 100% of grade is final. Attendance/psets optional

50% failure rate

Goal of policies

Guideline how to spend your time week by week

Components of course are complimentary: Lecture notes, lectures, psets, sections, OH, midterm/final

Collaboration policy: Get the benefits of true collaboration.

Why enforce / grade?

We are all human

Not everyone performs well under time pressure.

But final+midterm are still 45% of your grade.

Updates to collaboration policy

Can collaborate with one more pair: list their names on first page. (page without questions - skipped when grading on gradescope)

Not allowed: Collaboration groups in OH, talking to people outside your partner / extra pair, not citing sources for information, “divvying up” questions.

Wheels of honor code enforcement are slow but harsh.